用c++实现最优二叉搜索树先根序列打印

以下是用 C++ 实现最优二叉搜索树先根序列打印的示例代码：

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1005;
const int INF = 0x3f3f3f3f;

int n;
int keys[MAXN];
int freqs[MAXN];
int dp[MAXN][MAXN];
int root[MAXN][MAXN];

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

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> keys[i] >> freqs[i];
    }
    for (int i = 1; i <= n; i++) {
        dp[i][i] = freqs[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] = INF;
            for (int k = i; k <= j; k++) {
                int cost = dp[i][k - 1] + dp[k + 1][j] + freqs[k];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << "Optimal BST cost: " << dp[1][n] << endl;
    cout << "Optimal BST preorder: ";
    print_preorder(1, n);
    cout << endl;
    return 0;
}

其中，`keys[i]` 表示第 i 个关键字，`freqs[i]` 表示第 i 个关键字的频率，`dp[i][j]` 表示第 i 个关键字到第 j 个关键字构成的子树的最小代价，`root[i][j]` 表示第 i 个关键字到第 j 个关键字构成的子树的根节点。

首先，我们初始化每个单独的节点的代价和根节点。然后，我们从小到大枚举子树的长度，从左到右枚举子树的起点和终点，计算每个可能的根节点的代价，选取代价最小的作为该子树的根节点。最后，我们输出最优二叉搜索树的代价和先根序列。

注意，这里的先根序列是指先输出根节点，然后递归输出左子树和右子树。