【题解】加分二叉树

我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满本都写着四个字是‘区间DP’！

为什么是区间DP呢？因为是中序遍历啊！中序遍历有一个很大的特点就是，根在中间，二叉树的左右子树节点在根的左右对应。

那么我们只需要枚举根就好了，枚举根是不是就很像区间DP。对于一个区间，我们枚举分割点就相当于枚举根，然后一步步转移就好了，同时也要记录下每个区间的根是什么，也就是最优值是多少。

既然是DP，那也写一个转移方程吧（感觉题目已经给了诶）

因为dfs其实更好写，所以用dfs更方便。

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<stack>
#define fs first
#define se second
#define pb push_back
#define cppio ios::sync_with_stdio(false);cin.tie(0)
#define eps 1e-7 
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> VI;

const int maxn=1e2+6;
const ll inf=0x3f3f3f3f;
const ll mod=1e9+7;

ll a[maxn];
int n;
ll dp[maxn][maxn];
ll root[maxn][maxn];

ll dfs(int l,int r){
    if(dp[l][r]!=-1) return dp[l][r];
    if(l>r) return 1;
    if(l==r){
        root[l][r]=l;
        return a[l];
    } 
    dp[l][r]=0;
    for(int i=l;i<=r;i++){
        ll tmp=dfs(l,i-1)*dfs(i+1,r)+a[i];
        if(tmp>dp[l][r]){
            root[l][r]=i;
            dp[l][r]=tmp;
        }
    }
    return dp[l][r];
}

void dfs2(int l,int r){
    if(l>r) return ;
    printf("%lld ",root[l][r]);
    dfs2(l,root[l][r]-1);
    dfs2(root[l][r]+1,r);
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",a+i);
    }
    memset(dp,-1,sizeof(dp));
    printf("%lld\n",dfs(1,n));
    dfs2(1,n);
    return 0;
}