题意

• 一个1-base二叉树，n个结点，中序遍历为(1,2,3,...,n),每个点有一个val，选择一个子树的加分规则如下：
• 如果某个子树为空，就视为val=1，叶子节点分数为本身的分数
• 求符合中序遍历的加分最高的二叉树，输出加分和前序遍历

思路

• 对于一段中序遍历序号，总需要选择一个根，切分出左右子树计算价值
• 对于切分出的区间不断重复上述过程，得出整个树的最优解
• 那么大概就是一个区间dp，表示区间(i,j)最高分,
• 注意k如果是左右边界的时候需要强制置为1
• 对于还原根这个事，其实就是要在dp过程中保留每次取最优解的时候选择的根，所以再开一个path数组即可
• 最终还原前序遍历的时候dfs在处理到区间长度为2的时候继续往下处理会出现l=r和l>r两种情况，注意特殊处理

代码

#include<bits/stdc++.h>
using namespace std;
/**
 * dp[i][j]表示区间(i,j)最高分
 * pt[i][j]表示最高分的根
 * dp[i][j]=max(dp[i][j],dp[i][k-1]*dp[k+1][j]+val[k])
 */

int val[40];
long long dp[110][110],pt[110][110];
int n;

void dfs(int l,int r){
    if(l>r) return ;
    if(l==r){
        cout << pt[l][r] << ' ';
        return ;
    }
    //     if(r-l+1==2){
    //         cout << pt[l][r] << ' ' << l+r-pt[l][r] << ' ';
    //         return ;
    //     }
    cout << pt[l][r] << ' ';    
    dfs(l,pt[l][r]-1);
    dfs(pt[l][r]+1,r);
}

int main(){

    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> val[i];
        dp[i][i]=val[i];
        pt[i][i]=i;
    }
    for(int len=2;len<=n;len++){
        for(int i=1;i<=n;i++){
            int j=i+len-1;
            for(int k=i;k<=j;k++){
                if(dp[i][j]<(k==i?1:dp[i][k-1])*(k==j?1:dp[k+1][j])+val[k]){
                    dp[i][j]=(k==i?1:dp[i][k-1])*(k==j?1:dp[k+1][j])+val[k];
                    pt[i][j]=k;
                }
            }
        }
    }

    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=n;j++){
    //         cout << pt[i][j] << ' ';
    //     }
    //     cout << endl;
    // }

    cout << dp[1][n] << endl;
    dfs(1,n);
    return 0;
}