题解 | 加分二叉树

#include <bits/stdc++.h>
using namespace std;

// 前序打印构造函数
void printPreorder(int left, int right, vector<vector<int>>& bestRoot) {
    if (left > right) return;
    cout << bestRoot[left][right] + 1 << " ";  // 下标+1表示节点编号
    printPreorder(left, bestRoot[left][right] - 1, bestRoot);
    printPreorder(bestRoot[left][right] + 1, right, bestRoot);
}

int main() {
    int n;
    cin >> n;

    vector<int> score(n);  // 节点的分数
    vector<vector<int>> maxScore(n, vector<int>(n, 0)); // 区间最大加分
    vector<vector<int>> bestRoot(n, vector<int>(n, 0)); // 区间最优根位置

    // 读入分数
    for (int i = 0; i < n; ++i) {
        cin >> score[i];
        maxScore[i][i] = score[i];     // 单个节点加分就是自己
        bestRoot[i][i] = i;            // 根节点就是自己
    }

    // 区间DP
    for (int len = 2; len <= n; ++len) {
        for (int left = 0; left + len - 1 < n; ++left) {
            int right = left + len - 1;

            for (int rootPos = left; rootPos <= right; ++rootPos) {
                int leftScore = (rootPos - 1 < left) ? 1 : maxScore[left][rootPos - 1];
                int rightScore = (rootPos + 1 > right) ? 1 : maxScore[rootPos + 1][right];
                int curScore = leftScore * rightScore + score[rootPos];

                if (curScore > maxScore[left][right]) {
                    maxScore[left][right] = curScore;
                    bestRoot[left][right] = rootPos;
                }
            }
        }
    }

    // 输出最大加分
    cout << maxScore[0][n - 1] << endl;

    // 输出前序遍历结果
    printPreorder(0, n - 1, bestRoot);
    cout << endl;

    return 0;
}