用C语言完成如下题目的代码:1 最优二分检索树问题 分数 100 作者 李丽娜 单位 吉林大学 给定标识符集(a1​, a2​, …an​)，这些字符的下标从1开始按自然序编号，pi​是对ai​成功检索的概率, qi​是不成功检索的概率, 且∑(1<=i<=n)​pi​ +∑(0<=i<=n)​qi​ =1，问:它的最优二分检索树是怎样的？ 输入格式: 第1行是n，表示字符个数； 第2行是这n个字符的成功检索概率pi​, 0<pi​<1; 第3行是失败检索概率qi​，0<qi​<1，且∑(1<=i<=n)​pi​ +∑(0<=i<=n)​qi​ =1。 输出格式: 最优二分检索树先根遍历时得到的字符编号序列。 输入样例1: 4 0.1875 0.1875 0.0625 0.0625 0.125 0.1875 0.0625 0.0625 0.0625 输出样例1: 2 1 3 4 输入样例2: 5 0.1524 0.1369 0.0179 0.0007 0.3081 0.1567 0.1022 0.0682 0.0476 0.0084 0.0009 输出样例2: 2 1 5 3 4

以下是最优二分检索树问题的C语言代码实现，使用了动态规划算法：

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

#define MAX_N 100

int n; 
double p[MAX_N + 1];
double q[MAX_N + 1];
double w[MAX_N + 1][MAX_N + 1]; 
double e[MAX_N + 1][MAX_N + 1]; 
int root[MAX_N + 1][MAX_N + 1];

void optimal_bst() {
    int i, j, r, k;
    for (i = 1; i <= n + 1; i++) {
        w[i][i - 1] = q[i - 1];
        e[i][i - 1] = q[i - 1];
    }
    for (r = 0; r <= n; r++) {
        for (i = 1; i <= n - r + 1; i++) {
            j = i + r - 1;
            w[i][j] = w[i][j - 1] + p[j] + q[j];
            e[i][j] = INT_MAX;
            for (k = i; k <= j; k++) {
                double t = e[i][k - 1] + e[k + 1][j] + w[i][j];
                if (t < e[i][j]) {
                    e[i][j] = t;
                    root[i][j] = k;
                }
            }
        }
    }
}

void print_optimal_bst(int i, int j) {
    if (i <= j) {
        int r = root[i][j];
        printf("%d ", r);
        print_optimal_bst(i, r - 1);
        print_optimal_bst(r + 1, j);
    }
}

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

运行程序，输入样例即可得到输出结果。