#include <iostream>
#include <vector>
#include <climits>
using namespace std;

class OptimalBST {
public:
    pair<vector<vector<int>>, vector<vector<int>>> optimalBST(const vector<int>& keys, const vector<double>& probabilities) {
        int n = keys.size();
        vector<vector<int>> cost(n, vector<int>(n, 0));
        vector<vector<int>> root(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            cost[i][i] = probabilities[i];
            root[i][i] = i;
        }

        for (int length = 2; length <= n; length++) {
            for (int i = 0; i <= n - length; i++) {
                int j = i + length - 1;
                cost[i][j] = INT_MAX;
                double sum = 0;
                for (int k = i; k <= j; k++) sum += probabilities[k];

                for (int r = i; r <= j; r++) {
                    int leftCost = (r > i) ? cost[i][r-1] : 0;
                    int rightCost = (r < j) ? cost[r+1][j] : 0;
                    double totalCost = leftCost + rightCost + sum;

                    if (totalCost < cost[i][j]) {
                        cost[i][j] = totalCost;
                        root[i][j] = r;
                    }
                }
            }
        }
        return {cost, root};
    }

    void printOptimalBST(const vector<int>& keys, const vector<vector<int>>& root, int i, int j) {
        if (i > j) return;
        int r = root[i][j];
        cout << keys[r] << " ";
        printOptimalBST(keys, root, i, r-1);
        printOptimalBST(keys, root, r+1, j);
    }
};

int main() {
    int n;
    cout << "Enter the number of keys: ";
    cin >> n;

    vector<int> keys(n);
    vector<double> probabilities(n);

    cout << "Enter the keys: ";
    for (int i = 0; i < n; i++) {
        cin >> keys[i];
    }

    cout << "Enter the probabilities for each key: ";
    for (int i = 0; i < n; i++) {
        cin >> probabilities[i];
    }

    OptimalBST obst;
    auto [cost, root] = obst.optimalBST(keys, probabilities);

    cout << "Minimum search cost: " << cost[0][n-1] << endl;
    cout << "Optimal Binary Search Tree: ";
    obst.printOptimalBST(keys, root, 0, n-1);
    cout << endl;

    return 0;
}