给定标识符集(a 1 ​ , a 2 ​ , …a n ​ )，这些字符的下标从1开始按自然序编号，p i ​ 是对a i ​ 成功检索的概率, q i ​ 是不成功检索的概率, 且∑ (1<=i<=n) ​ p i ​ +∑ (0<=i<=n) ​ q i ​ =1，问:它的最优二分检索树是怎样的？ 输入格式: 第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语言代码

以下是使用C++实现的代码，与使用C语言实现的方法基本相同：

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

const int N = 500;
double p[N], q[N], w[N][N], c[N][N];
int root[N][N];

void opt_bst(int n) {
    for (int i = 1; i <= n; i++) {
        c[i][i] = w[i][i] = q[i];
        root[i][i] = i;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            c[i][j] = 1e9;
            for (int k = i; k <= j; k++) {
                double tmp = c[i][k - 1] + c[k + 1][j] + w[i][j];
                if (tmp < c[i][j]) {
                    c[i][j] = tmp;
                    root[i][j] = k;
                }
            }
        }
    }
}

void dfs(int l, int r) {
    if (l > r) return;
    int k = root[l][r];
    cout << k << " ";
    dfs(l, k - 1);
    dfs(k + 1, r);
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        w[i][i] = q[i] = p[i];
    }
    for (int i = 0; i <= n; i++) {
        w[i][i-1] = q[i];
        c[i][i-1] = 0;
    }
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i <= n - len + 1; i++) {
            int j = i + len - 1;
            w[i][j] = w[i][j-1] + p[j] + q[j];
        }
    }
    opt_bst(n);
    cout << "先根遍历序列：";
    dfs(1, n);
    cout << endl;
    return 0;
}