一道比较经典的区间dp题目

首先我们设dp[i][j]表示我们用i-j这些点构造树的最大收益是多少

首先dp[i][i]=a[i]（只有一个点，最大价值即点本身价值）

现在，我们考虑转移：

因为一颗子树的价值=左子树价值*右子树价值+根价值

那么，如果我们知道了根，左子树，右子树后，就可以进行转移了

于是，我们先枚举根，但是，如果再枚举哪些点放左子树，哪些放右子树的话，明显复杂度就爆炸了，怎么办呢？

注意到，题目有个条件：树的中序遍历为1...n，那么，就有一个小性质：

i的左子树都是编号比i小的点，i的右子树都是编号比i大的点。

于是，如果我们枚举了根的话，假设为k，那么就有:

左子树组成的点：l...k-1

右子树组成的点:k+1...r

注意到，这是两个连续的区间，那么转移过来直接使用dp[l][k-1]和dp[k+1][r]的值即可

于是有转移：

但是需要注意的是，我们枚举根的过程中，如果k==i||k==j,如果我们不做处理的话，会使得dp[i][k-1]||dp[k+1][j]的值为0，导致转移错误，所以，为了正确的转移，我们需要在开始的时候，把所有的dp[i][i-1]的值赋为1

而，转移过程中，为了保证转移正确性，我们观察式子，i大的要先算所以我们倒着枚举i，j小的要后算，所以我们顺着枚举j，就行了。

至于输出前序遍历，我们可以直接对区间枚举根，然后看看是否是有这个枚举的根转移过来的，若是，当前区间的根即是这个，否则继续枚举就行了。

当然，你也可以在dp转移的时候，同时维护下每个区间的根

代码:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=31;
int a[N],dp[N][N],n;
inline void dfs(int l,int r){
    if(l>r){
        return;
    }
    if(l==r){
        printf("%d ",l);
        return;
    }
    for(int i=l;i<=r;++i){
        if(dp[l][r]==dp[l][i-1]*dp[i+1][r]+a[i]){
            printf("%d ",i);
            dfs(l,i-1),dfs(i+1,r);
            return;
        }
    }
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&a[i]);
        dp[i][i]=a[i];dp[i][i-1]=1;
    }
    dp[n+1][n]=1;
    for(int i=n;i;--i){
        for(int j=i+1;j<=n;++j){
            for(int k=i;k<=j;++k){
                dp[i][j]=max(dp[i][j],dp[i][k-1]*dp[k+1][j]+a[k]);
            }
        }
    }
    printf("%d\n",dp[1][n]);
    dfs(1,n);
    return 0;
}