import java.util.*;

public class Main {
    
   public static void bst(double[] p, double[] q, int n) {
    double[][] w = new double[n + 1][n + 1];
    double[][] c = new double[n + 1][n + 1];
    int[][] r = new int[n + 1][n + 1];

    // Initialization
    for (int i = 0; i <= n; i++) {
        w[i][i] = q[i];
        c[i][i] = 0;
        r[i][i] = 0;
    }

    // Building matrices
    for (int m = 1; m <= n; m++) {
        for (int i = 0; i <= n - m; i++) {
            int j = i + m;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            double mincost = Double.MAX_VALUE;
            int root = -1;

            for (int k = (i < j - 1 ? r[i][j - 1] : i); k <= (j > i + 1 ? r[i + 1][j] : j); k++) {
                double cost = (i <= k - 1 ? c[i][k - 1] : 0) + (k <= j ? c[k][j] : 0) + w[i][j];
                if (cost < mincost) {
                    mincost = cost;
                    root = k;
                }
            }

            c[i][j] = mincost;
            r[i][j] = root;
        }
    }

    // Print W, C, R values
    printDiagonalMatrices(w, c, r, n);

    // Final output
    System.out.println("\nMinimum cost: " + c[0][n]);
    System.out.println("Weight : " + w[0][n]);
}

// Helper method to print W, C, R values in the desired format
public static void printDiagonalMatrices(double[][] w, double[][] c, int[][] r, int n) {
    System.out.println("Diagonal Representation of W, C, R Matrices:");

    for (int d = 0; d <= n; d++) { // d = j - i
        System.out.println("\nFor j - i = " + d + ":");
        for (int i = 0; i <= n - d; i++) {
            int j = i + d;
            System.out.printf("W[%d][%d] = %.2f, C[%d][%d] = %.2f, R[%d][%d] = %d\n", 
                              i, j, w[i][j], i, j, c[i][j], i, j, r[i][j]);
        }
    }
}


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of keys: ");
        int n = sc.nextInt();

        double[] p = new double[n + 1];
        double[] q = new double[n + 1];

        System.out.println("Enter probabilities for the keys:");
        for (int i = 1; i <= n; i++) {
            System.out.print("p[" + i + "]: ");
            p[i] = sc.nextDouble();
        }

        System.out.println("Enter probabilities for the dummy keys:");
        for (int i = 0; i <= n; i++) {
            System.out.print("q[" + i + "]: ");
            q[i] = sc.nextDouble();
        }

        bst(p, q, n);
    }
}