class BSTDynamic{
    static int[] p; 
    public static double C(int n)
    {
        double[][] C = new double [n+1][n+1];
        double sum_left, sum_right, sump, min_cost;
        for (int i = 0; i < n; i++){
            C[i][i] = p[i];
            for(int length = 1; length < n; length++){
                // check all intervals of this length
                for (int Left = 1; Left < n - length; Left++){
                    int Right = Left + length;

                    sump = 0.0; // sum probabilities
                    for( int k = Left; k <= Right; k++){
                        sump = sump + p[k];
                    }

                    min_cost = Integer.MAX_VALUE;
                    for(int k = Left; k <= Right; k++){
                        sum_left = (Left < k ?  C[Left][k-1]: 0.0);
                        sum_right =  (Right > k ? C[k+1][Right]: 0.0);
                        double this_cost =  sum_left + sump + sum_right;
                        min_cost = Math.min(this_cost, min_cost);
                    } 
                    C[Left][Right] = min_cost;     
                }
            }
        }
        return (C[1][n]);
    }
}