import java.util.Scanner;

public class OBSTree {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // Get the number of keys
        System.out.print("Enter the number of keys: ");
        int n = scanner.nextInt();

        // Input probabilities for keys (P array)
        double[] P = new double[n];
        System.out.println("Enter probabilities for the keys:");
        for (int i = 0; i < n; i++) {
            System.out.print("P[" + i + "]: ");
            P[i] = scanner.nextDouble();
        }

        // Input probabilities for dummy nodes (Q array)
        double[] Q = new double[n + 1];
        System.out.println("Enter probabilities for the dummy nodes:");
        for (int i = 0; i <= n; i++) {
            System.out.print("Q[" + i + "]: ");
            Q[i] = scanner.nextDouble();
        }

        // Call the OBST procedure
        OBSTResult result = OBST(P, Q, n);

        // Print the cost and root matrices
        System.out.println("\nCost Matrix C:");
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.printf("%.2f ", result.C[i][j]);
            }
            System.out.println();
        }

        System.out.println("\nRoot Matrix R:");
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= n; j++) {
                System.out.printf("%d ", result.R[i][j]);
            }
            System.out.println();
        }

        // Print the optimal cost
        System.out.printf("\nThe optimal cost is: %.2f\n", result.C[0][n]);
    }

    public static OBSTResult OBST(double[] P, double[] Q, int n) {
        double[][] C = new double[n + 1][n + 1];
        double[][] W = new double[n + 1][n + 1];
        int[][] R = new int[n + 1][n + 1];

        // Initialize for single nodes and dummy nodes
        for (int i = 0; i <= n; i++) {
            W[i][i] = Q[i];
            C[i][i] = 0;
            R[i][i] = 0;
            if (i < n) {
                W[i][i + 1] = Q[i] + Q[i + 1] + P[i];
                C[i][i + 1] = W[i][i + 1];
                R[i][i + 1] = i + 1;
            }
        }

        // Compute the OBST for all subarrays of length >= 2
        for (int m = 2; m <= n; m++) { // Tree size
            for (int i = 0; i <= n - m; i++) {
                int j = i + m;
                W[i][j] = W[i][j - 1] + P[j - 1] + Q[j];

                // Find optimal root in range that minimizes cost
                double minCost = Double.MAX_VALUE;
                int bestRoot = -1;

                // Apply Knuth's optimization to reduce the number of root checks
                for (int k = R[i][j - 1]; k <= R[i + 1][j]; k++) {
                    double cost = C[i][k - 1] + C[k][j];
                    if (cost < minCost) {
                        minCost = cost;
                        bestRoot = k;
                    }
                }

                C[i][j] = W[i][j] + minCost;
                R[i][j] = bestRoot;
            }
        }

        // Return the computed cost and root matrices
        return new OBSTResult(C, W, R);
    }
}

// Helper class to store the results of the OBST function
class OBSTResult {
    double[][] C;
    double[][] W;
    int[][] R;

    OBSTResult(double[][] C, double[][] W, int[][] R) {
        this.C = C;
        this.W = W;
        this.R = R;
    }
}