题解 | #加分二叉树#

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 30;

int n;
int w[N];
int f[N][N], g[N][N];


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

}
int main() {
    cin >> n;
    for(int i = 1; i <=n; i++) cin >> w[i];
    for(int len = 1; len <= n; len ++) {
        for(int l = 1; l + len -1 <=n; l++) {
            int r = l + len - 1;
            // 区间长度为1，表示节点没有子树，看作是叶子节点，对应的得分就是自身的 w值
            if(len == 1){
                f[l][r] = w[l];
                //根节点就是自己
                g[l][r] = l;
            }else{
                for(int k = l; k <= r; k++){
                    //k==l时表示 左子树空，只有右子树，left表示 以k为根节点的左子树的得分（f[l][k-1]）=1
                    int left = k == l ? 1 : f[l][k-1];
                    int right = k == r ? 1 : f[k+1][r];
                    int score = left * right + w[k];
                    if(f[l][r] < score){
                        f[l][r] = score;
                        //g[l][r]保存了中序序列中某一段，加分最高的二叉树的根
                        g[l][r] = k;
                    }
                }
            }

        }
    }
    cout << f[1][n] << endl;
    print(1,n);
    return 0;
}
// 64 位输出请用 printf("%lld")