最优二分检索树问题,写出满足如下要求的C++代码，输入格式: 第1行是n，表示字符个数； 第2行是这n个字符的成功检索概率p i ​ , 0<p i ​ <1; 第3行是失败检索概率q i ​ ，0<q i ​ <1，且∑ (1<=i<=n) ​ p i ​ +∑ (0<=i<=n) ​ q i ​ =1输出最优二分检索树先根遍历时得到的字符编号序列。

以下是最优二分检索树问题的C++代码实现：

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

const int MAXN = 1005;
double p[MAXN], q[MAXN], dp[MAXN][MAXN], w[MAXN][MAXN];
int root[MAXN][MAXN], ans[MAXN];

void dfs(int l, int r, int cur) {
    if (l > r) return;
    ans[root[l][r]] = cur;
    dfs(l, root[l][r] - 1, cur + 1);
    dfs(root[l][r] + 1, r, cur + 1);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
    }
    for (int i = 0; i <= n; i++) {
        cin >> q[i];
    }
    memset(dp, 0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        dp[i][i] = q[i - 1] + p[i] + q[i];
        w[i][i] = dp[i][i];
        root[i][i] = i;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int j = i + len - 1;
            for (int k = i; k <= j; k++) {
                double tmp = dp[i][k - 1] + dp[k + 1][j] + w[i][j];
                if (tmp < dp[i][j]) {
                    dp[i][j] = tmp;
                    root[i][j] = k;
                }
            }
            w[i][j] = w[i][j - 1] + q[j] + p[j];
        }
    }
    dfs(1, n, 1);
    cout << "先根遍历时得到的字符编号序列为：";
    for (int i = 1; i <= n; i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

输入格式：
第1行是n，表示字符个数；
第2行是这n个字符的成功检索概率pi，0<pi<1；
第3行是失败检索概率qi，0<qi<1，且∑(1<=i<=n)pi+∑(0<=i<=n)qi=1

输出格式：
先根遍历时得到的字符编号序列。

输入样例：
5
0.15 0.1 0.05 0.1 0.2
0.05 0.1 0.05 0.05 0.05 0.1

输出样例：
先根遍历时得到的字符编号序列为：4 2 1 3 5