P1040 [NOIP 2003 提高组] 加分二叉树

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

const int MAXN = 35;

int d[MAXN];                  // 各节点分数
long long f[MAXN][MAXN];      // f[l][r]：区间 [l,r] 子树的最高加分
int root[MAXN][MAXN];         // f[l][r] 对应的根节点

void buildPre(int l, int r, vector<int> &out) {
    if (l > r) return;
    int k = root[l][r];
    out.push_back(k);
    buildPre(l, k - 1, out);
    buildPre(k + 1, r, out);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> d[i];

    // 空子树的加分为 1：f[i][i-1] = 1
    for (int i = 1; i <= n + 1; i++) f[i][i - 1] = 1;

    // 叶子：加分就是它自己的分数
    for (int i = 1; i <= n; i++) {
        f[i][i] = d[i];
        root[i][i] = i;
    }

    for (int len = 2; len <= n; len++) {
        for (int l = 1; l + len - 1 <= n; l++) {
            int r = l + len - 1;
            f[l][r] = 0;
            for (int k = l; k <= r; k++) {
                long long val = f[l][k - 1] * f[k + 1][r] + d[k];
                if (val > f[l][r]) {
                    f[l][r] = val;
                    root[l][r] = k;
                }
            }
        }
    }

    cout << f[1][n] << "\n";

    vector<int> pre;
    buildPre(1, n, pre);
    for (int i = 0; i < (int)pre.size(); i++) {
        if (i) cout << " ";
        cout << pre[i];
    }
    cout << "\n";

    return 0;
}