#include <stdio.h>
#include <conio.h>

#define MAX 10
#define INF 99999
int main()return 0; {
    int n, i, j, k;
    printf("Enter number of keys: ");
    scanf("%d", &n);
    float p[MAX], q[MAX], w[MAX][MAX], c[MAX][MAX];
    int r[MAX][MAX];
    printf("Enter probabilities p1..pn (key probabilities):\n");
    for (i = 1; i <= n; i++) 
        scanf("%f", &p[i]);
    printf("Enter probabilities q0..qn (dummy probabilities):\n");
    for (i = 0; i <= n; i++) 
        scanf("%f", &q[i]);
    for (i = 0; i <= n; i++) {
        w[i][i] = q[i];
        c[i][i] = 0;
        r[i][i] = 0;
    }
    for (int m = 1; m <= n; m++) {
        for (i = 0; i <= n - m; i++) {
            j = i + m;
            w[i][j] = w[i][j-1] + p[j] + q[j];
            float min = INF;
            int root = 0;
            for (k = i + 1; k <= j; k++) {
                float cost = c[i][k-1] + c[k][j];
                if (cost < min) {
                    min = cost;
                    root = k;
                }
            }
            c[i][j] = w[i][j] + min;
            r[i][j] = root;
        }
    }
    printf("\nOptimal BST Cost = %.2f\n", c[0][n]);
    printf("\nRoot Table (r[i][j]):\n");
    for (i = 0; i <= n; i++) {
        for (j = 0; j <= n; j++)
            printf("%2d ", r[i][j]);
        printf("\n");
    }
    getch();
}