#include <stdio.h>
#include <limits.h>
#define MAX 100
int w[MAX][MAX], c[MAX][MAX], r[MAX][MAX];
void obst(int p[], int q[], int n);
int find(int c[][MAX], int r[][MAX], int i, int j);
void inorder(int r[][MAX], int i, int j, int p[]);
void obst(int p[], int q[], int n) {
int i, j, m, k;
// Initialize for empty and single keys
for (i = 0; i <= n; i++) {
w[i][i] = q[i];
c[i][i] = 0;
r[i][i] = 0;
}
// Initialize for trees with two keys
for (i = 0; i < n; i++) {
w[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
c[i][i + 1] = q[i] + q[i + 1] + p[i + 1];
r[i][i + 1] = i + 1;
}
// Handle the last dummy key
w[n][n] = q[n];
c[n][n] = 0;
r[n][n] = 0;
// Dynamic programming to calculate costs
for (m = 2; m <= n; m++) { // m is the size of the subtree
for (i = 0; i <= n - m; i++) {
j = m + i;
w[i][j] = w[i][j - 1] + q[j] + p[j];
k = find(c, r, i, j);
c[i][j] = w[i][j] + c[i][k - 1] + c[k][j];
r[i][j] = k;
}
}
// Print cost and weight tables
for (i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
printf("w[%d][%d] :%d\t", i, j, w[i][j]);
}
printf("\n");
for (int j = 0; j <= n; j++) {
printf("c[%d][%d] :%d\t", i, j, c[i][j]);
}
printf("\n");
}
// Print the maximum cost of the OBST
printf("Maximum cost of the OBST: %d\n", c[0][n]);
}
int find(int c[][MAX], int r[][MAX], int i, int j) {
int min = INT_MAX, l;
for (int m = r[i][j - 1]; m <= r[i + 1][j]; m++) {
if (c[i][m - 1] + c[m][j] < min) {
min = c[i][m - 1] + c[m][j];
l = m;
}
}
return l;
}
void inorder(int r[][MAX], int i, int j, int p[]) {
if (i < j) {
int root = r[i][j];
inorder(r, i, root - 1, p);
printf("%d ", p[root]); // Visit root (keys are 1-indexed)
inorder(r, root, j, p);
}
}
int main() {
int p[MAX], q[MAX], i, n;
printf("Enter size: ");
scanf("%d", &n);
printf("Enter probabilities of p (0 is assumed for p[0]):\n");
for (i = 1; i <= n; i++) {
printf("p[%d]: ", i);
scanf("%d", &p[i]);
}
p[0] = 0; // Probability for p[0] (dummy key)
printf("Enter probabilities of q (for q[0] to q[%d]):\n", n);
for (i = 0; i <= n; i++) {
printf("q[%d]: ", i);
scanf("%d", &q[i]);
}
printf("Calculating OBST:\n");
obst(p, q, n);
printf("Inorder traversal of the OBST:\n");
inorder(r, 0, n, p);
printf("\n");
return 0;
}