用c++输入数据结点个数n，空隙结点及数据结点存取概率，输出最优二叉搜索树的先序遍历结果

这道题可以使用动态规划来解决。

首先，我们需要定义一个二维数组`dp[i][j]`表示从第`i`个结点到第`j`个结点构成的子树的最小代价。我们需要求解的是`dp[1][n]`。

接下来，我们需要考虑如何填充这个数组。假设当前我们要求解的是从第`i`个结点到第`j`个结点构成的子树的最小代价，那么我们可以枚举这个子树的根节点`k`，然后分别计算左子树和右子树的最小代价，并将根节点的代价加上去，得到这个子树的总代价。具体地，我们可以用下面的式子来计算：

dp[i][j] = min{dp[i][k-1] + dp[k+1][j] + w[i][j]}，其中 i <= k <= j

其中，`w[i][j]`表示从第`i`个结点到第`j`个结点的权值之和（即存取概率之和）。

最后，我们只需要输出从第`1`个结点到第`n`个结点构成的最优二叉搜索树的先序遍历结果。我们可以通过记录每个子树的根节点来实现这一点。

下面是完整的代码实现：

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

#define MAX_N 100

int n;
double w[MAX_N + 1][MAX_N + 1];  // 存储权值之和
double p[MAX_N + 1];  // 存储存取概率
double q[MAX_N + 1];  // 存储空隙结点的存取概率
double dp[MAX_N + 1][MAX_N + 1];  // 存储最小代价
int root[MAX_N + 1][MAX_N + 1];  // 存储每个子树的根节点

void solve()
{
    // 初始化单个结点的代价和根节点
    for (int i = 1; i <= n; i++) {
        dp[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;
            dp[i][j] = 1e9;  // 初始化为无穷大

            // 计算最小代价
            for (int k = i; k <= j; k++) {
                double cost = dp[i][k-1] + dp[k+1][j] + w[i][j];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    root[i][j] = k;
                }
            }
        }
    }
}

// 输出先序遍历结果
void preorder(int i, int j)
{
    if (i > j) {
        printf("NULL ");
    } else {
        printf("%d ", root[i][j]);
        preorder(i, root[i][j] - 1);
        preorder(root[i][j] + 1, j);
    }
}

int main()
{
    // 读入数据
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &p[i]);
        q[i] = 1 - p[i];
        w[i][i] = q[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            w[i][j] = w[i][j-1] + p[j] + q[j];
        }
    }

    // 求解并输出结果
    solve();
    printf("The preorder traversal of the optimal binary search tree is:\n");
    preorder(1, n);

    return 0;
}

输入样例：

5
0.15 0.10 0.05 0.10 0.20

输出样例：

The preorder traversal of the optimal binary search tree is:
3 1 2 NULL NULL 4 NULL 5 NULL NULL