记录编号	602873	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	KKZH	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2025-07-06 12:40:26	内存使用	3.73 MiB

#include <bits/stdc++.h>
using namespace std;
const long long N = 100;
long long n;
long long a[N], dp[N][N], fi[N][N];

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

int main() {
		freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);

    cin >> n;
    // 初始化所有i>j的dp值为1（空子树加分）
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 0; j < i; j++) {
            dp[i][j] = 1;
        }
    }
    // 输入节点分数并初始化单个节点
    for (long long i = 1; i <= n; i++) {
        cin >> a[i];
        dp[i][i] = a[i];
        fi[i][i] = i; // 单个节点的根节点为自己
    }
    // 动态规划计算最大加分
    for (long long len = 2; len <= n; len++) {
        for (long long l = 1; l <= n - len + 1; l++) {
            long long r = l + len - 1;
            dp[l][r] = 0; // 初始化为0，因为要取最大值
            for (long long rt = l; rt <= r; rt++) {
                long long left_score = dp[l][rt - 1];
                long long right_score = dp[rt + 1][r];
                long long score = left_score * right_score + a[rt];
                if (score > dp[l][r]) {
                    dp[l][r] = score;
                    fi[l][r] = rt;
                }
            }
        }
    }
    cout << dp[1][n] << endl;
    if (n > 0) {
        int root = fi[1][n];
        cout << root; // 先输出整棵树的根节点（无空格）
        dfs(1, root - 1); // 递归输出左子树（带空格前缀）
        dfs(root + 1, n); // 递归输出右子树（带空格前缀）
    }
    cout << endl;
    return 0;
}