数据集 S＝< 1, 2, ..., n > 存取概率分布P = < a0, b1, a1, b2, … , ai, bi+1, …, bn, an >(b0 = 0), 求一棵最优的(即平均比较次数最少的)二分检索树. 假设 m[i,j] 是相对于输入 S[i,j] 和 P[i,j] 的最优二叉搜索树的平均比较次数，令m[i,i-1]=0. 【输入形式】输入数据结点个数n，空隙结点及数据结点存取概率 【输出形式】最优二叉搜索树的先序遍历结果 【样例输入】 5 0.04 0.1 0.02 0.3 0.02 0.1 0.05 0.2 0.06 0.1 0.01 【样例输出】 2 1 4 3 5 编写c++代码

以下是使用动态规划求解最优二叉搜索树的 C++ 代码：

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

// 动态规划求解最优二叉搜索树
void optimal_bst(int n, vector<double>& p, vector<double>& q, vector<vector<double>>& w, vector<vector<int>>& root) {
    // 初始化单节点树的情况
    for (int i = 1; i <= n + 1; i++) {
        w[i][i - 1] = q[i - 1];
        root[i][i - 1] = i - 1;
    }
    // 枚举区间长度
    for (int len = 1; len <= n; len++) {
        // 枚举区间起点
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            w[i][j] = numeric_limits<double>::max();
            // 枚举根节点
            for (int k = i; k <= j; k++) {
                double cost = w[i][k - 1] + w[k + 1][j] + q[i - 1] + q[k] + p[k];
                if (cost < w[i][j]) {
                    w[i][j] = cost;
                    root[i][j] = k;
                }
            }
        }
    }
}

// 输出最优二叉搜索树的先序遍历结果
void print_optimal_bst(int i, int j, const vector<vector<int>>& root) {
    if (i > j) {
        return;
    }
    int k = root[i][j];
    cout << k << " ";
    print_optimal_bst(i, k - 1, root);
    print_optimal_bst(k + 1, j, root);
}

int main() {
    int n;
    cin >> n;
    vector<double> p(n + 1), q(n + 1); // 存取概率
    vector<vector<double>> w(n + 2, vector<double>(n + 1)); // 子树的期望代价
    vector<vector<int>> root(n + 1, vector<int>(n + 1)); // 最优子树的根节点
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 0; i <= n; i++) {
        cin >> q[i];
    }
    optimal_bst(n, p, q, w, root);
    print_optimal_bst(1, n, root);
    return 0;
}

输入样例：

5
0.04 0.1 0.02 0.3 0.02 0.1 0.05 0.2 0.06 0.1 0.01

输出样例：

2 1 4 3 5