题解 | 加分二叉树

#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 << " ";
    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>> bestScore(n, vector<int>(n, 0));
    vector<vector<int>> bestRoot(n, vector<int>(n, 0));
    for (int i = 0; i < n; i++) {
        cin >> score[i];
        bestScore[i][i] = score[i];
        bestRoot[i][i] = i;
    }

    for (int len = 2; len <= n; len++) {
        for (int i = 0; i + len - 1 < n; i++) {
            int j = i + len - 1;
            for (int r = i; r <= j; r++) {
                int leftScore = (r - 1 < i) ? 1 : bestScore[i][r - 1];
                int rightScore = (r + 1 > j) ? 1 : bestScore[r + 1][j];
                int curScore = leftScore * rightScore + score[r];
                if (curScore > bestScore[i][j]) {
                    bestScore[i][j] = curScore;
                    bestRoot[i][j] = r;
                }
            }
        }
    }
    cout << bestScore[0][n - 1] << endl;
    printPreOrder(0, n - 1, bestRoot);
    cout << endl;
    return 0;
}
// 64 位输出请用 printf("%lld")