题解 | #加分二叉树#

解题思路：

• 问题分析为对于一个中序输入的树，根据规则找出组合积分最大值，即是以输入$v_{i}v\_i$做为$rootroot$，枚举每一个$rootroot$构成的树形所得到的最大积分。
• 对于每一个构成这棵树的子树也同样符合规则，从节点数$2\to n2\; \backslash to\; n$进行枚举每一个组合选出最大组合积分。令$d{p}_{l,r}dp\_\{l,r\}$表示从编号$ll$到编号$rr$的最大积分值，则很容易得到状态转移方程：$d{p}_{l,r}=\max (d{p}_{l,r},d{p}_{l,root-1}+d{p}_{root+1,r}+v_{root})dp\_\{l,r\}\; =\; \backslash max(dp\_\{l,r\},\; dp\_\{l,root-1\}\; +\; dp\_\{root+1,\; r\}\; +\; v\_\{root\})$
• 同时可以记录每个区间中的产生最大值的$rootroot$，最后递归输出即可。

#include<bits/stdc++.h>
using namespace std;
void print_root(int l, int r, vector<vector<int>> &record){
    if (l > r) return;
    cout<< record[l][r]+1<<" ";
    print_root(l, record[l][r] - 1 , record);
    print_root(record[l][r] + 1, r, record);
}
int main(){
    int n;
    cin >>n;
    vector<int> v(n);
    vector<vector<int>> dp(n,vector<int> (n));
    vector<vector<int>> record(n, vector<int>(n));
    for(int i = 0; i < n; ++i){
        cin>> v[i];
        dp[i][i] = v[i];//对于单节点区间中的积分值就是其自己
        record[i][i] = i;//对于单节点区间中的root亦是其自己
        }
    for(int len = 2; len <= n; ++len){
        int mx_l, mx_r,mx_root;
        for(int l = 0; l < n; ++l){
            int r = l + len - 1;
            if(r >= n) break;
            for(int root = l; root <= r; ++root){
                int tmp = (root-1 < l ? 1: dp[l][root-1]) * (root+1 > r? 1: dp[root+1][r]) + v[root];
                if(tmp > dp[l][r]) {
                    dp[l][r] = tmp;
                    record[l][r] = root;
                }
                
            }
        }
    }
    cout<<dp[0][n-1]<<endl;
    print_root(0,n-1,record);
    return 0;
}