最优二分检索树问题,写出满足如下要求的C++代码，输出最优二分检索树先根遍历时得到的字符编号序列。

以下是最优二分检索树问题的C++代码实现：

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

void printOptimalBST(vector<vector<int>>& root, int i, int j, int parent) {
    if (i > j) return;
    if (parent == 0) cout << "k" << root[i][j] << " is root" << endl;
    else {
        if (j < parent) cout << "k" << root[i][j] << " is left child of " << "k" << parent << endl;
        else cout << "k" << root[i][j] << " is right child of " << "k" << parent << endl;
    }
    printOptimalBST(root, i, root[i][j] - 1, root[i][j]);
    printOptimalBST(root, root[i][j] + 1, j, root[i][j]);
}

void optimalBST(vector<int>& keys, vector<int>& freq) {
    int n = keys.size();
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
    vector<vector<int>> root(n + 1, vector<int>(n + 1, 0));

    for (int i = 0; i < n; i++) {
        dp[i][i] = freq[i];
        root[i][i] = i;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i <= n - len; i++) {
            int j = i + len - 1;
            dp[i][j] = INT_MAX;
            for (int k = i; k <= j; k++) {
                int cost = ((k > i) ? dp[i][k - 1] : 0) +
                           ((k < j) ? dp[k + 1][j] : 0) +
                           freq[k];
                if (cost < dp[i][j]) {
                    dp[i][j] = cost;
                    root[i][j] = k;
                }
            }
        }
    }

    cout << "The optimal BST cost is: " << dp[0][n - 1] << endl;
    cout << "The optimal BST is: " << endl;
    printOptimalBST(root, 0, n - 1, 0);
}

int main() {
    vector<int> keys = {10, 12, 16, 21};
    vector<int> freq = {4, 2, 6, 3};
    optimalBST(keys, freq);
    return 0;
}

其中，`optimalBST`函数使用动态规划求解最优二分检索树的成本，并构造出最优二分检索树。`printOptimalBST`函数则用于输出最优二分检索树的先根遍历序列，其中`root`数组保存了每个子树的根节点编号。