public class JoinOrder  {

    // input
    double[] f;
    int[] c;

    double[][] m; // costs
    int lastChange[][]; // split matrix
    double[][] s; // size of intermediate results


    public JoinOrder(int[] c, double[] f) {
	this.c = c;
	this.f = f;
    }

    public void compute(boolean debug) {
	if (c.length != 0) {
	    dp();
	    if (debug)
		debug();
	}
    }
  

    public void dp()   {

	// shortcuts
	int n = c.length;

	m = new double [n][n];
	lastChange = new int [n][n];
	s = new double [n][n];

	// initialize intermediate results of single relations
	for (int i = 0; i<n; ++i)
	    s[i][i] = c[i];
		

	for( int k = 2; k <= n; ++k ) { // how many joins of length k

	    for( int left = 0; left <= n - k ; ++left )  {

		int right = left + k - 1;
		m[ left ][ right ] = Double.MAX_VALUE;
		s[left][right] = f[right-1] 
		    * s[left][right-1] * s[right][right];

		for( int i = left; i < right; ++i )  { // choose split
		    
		    // calculate costs according to given cost function
		    double thisCost = m[left][i] + m[i+1][right] 
			+ s[left][i] * s[i+1][right] * f[i];

		    if( thisCost < m[ left ][ right ] )  {
			// select minimum
			m[ left ][ right ] = thisCost;
			lastChange[ left ][ right ] = i;
		    }
		}

	    }

	}
	

    }

    // prints the intermediate results
    public void debug() {
	int joinCount = c.length;

	System.out.println("S");

	for( int i = 0; i < joinCount; i++ )  {
	    for( int j = 0; j < joinCount; j++ ) {
		System.out.print( s[ i ][ j ] + "    " );
	    }
	    System.out.println( );
	}

	System.out.println("M");

	for( int i = 0; i < joinCount; i++ )  {
	    for( int j = 0; j < joinCount; j++ ) {
		System.out.print( m[ i ][ j ] + "    " );
	    }
	    System.out.println( );
	}

	System.out.println("lastchange");
           
	for( int i = 0; i < joinCount; i++ )   {
	    for( int j = 0; j < joinCount; j++ ) {
                    System.out.print( lastChange[ i ][ j ] + "    " );
	    }
	    System.out.println( );
	}

	System.out.println();
    }

    public void print() {
	System.out.print("(");
	extractsubplan(0, c.length-1);
	System.out.print(")");
	System.out.println();
    }

    public void extractsubplan(int i, int j) {
	if (j>i) {
	    System.out.print("(");
	    extractsubplan(i, lastChange[i][j]);
	    System.out.print(")");
	    System.out.print("(");
	    extractsubplan(lastChange[i][j]+1, j);
	    System.out.print(")");
	    return;
	} else {
	    System.out.print(i);
	    return;
	}
    }


    public static void main( String [ ] args )     {
	int[] c = {20, 10, 5, 200};
	double[] f = { 0.1, 0.1, 1};
	JoinOrder o = new JoinOrder(c, f);
	o.compute(true);
	o.print();

    }

}