给定标识符集(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语言实现，完整的代码如下：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100

int n;
double p[MAXN + 1], q[MAXN + 1];
double dp[MAXN + 1][MAXN + 1];
int root[MAXN + 1][MAXN + 1];

double sum(double arr[], int i, int j) {
    double res = 0;
    for (int k = i; k <= j; k++) {
        res += arr[k];
    }
    return res;
}

void preorderTraversal(int preorder[], int i, int j) {
    if (i > j) return;
    preorder[preorder[0]++] = root[i][j];
    preorderTraversal(preorder, i, root[i][j]-1);
    preorderTraversal(preorder, root[i][j]+1, j);
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &p[i]);
    }
    for (int i = 0; i <= n; i++) {
        scanf("%lf", &q[i]);
    }

    // 初始化dp数组
    for (int i = 1; i <= n; i++) {
        dp[i][i] = p[i] + q[i-1] + 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;
            dp[i][j] = 1e9;
            for (int k = i; k <= j; k++) {
                double val = dp[i][k-1] + dp[k+1][j] + sum(p, i, j) + sum(q, i-1, j);
                if (val < dp[i][j]) {
                    dp[i][j] = val;
                    root[i][j] = k;
                }
            }
        }
    }

    // 输出先根遍历序列
    int preorder[MAXN + 1] = {1, 0};
    preorderTraversal(preorder, 1, n);
    for (int i = 1; i <= n; i++) {
        printf("%d ", preorder[i]);
    }

    return 0;
}

该实现与上面的Java实现类似，区别在于C语言没有自带动态数组和List，需要手动管理数组的长度。同时，由于C语言数组下标从0开始，需要对sum函数和输出preorder数组的代码进行微调。