本题在洛谷上的链接：https://www.luogu.org/problemnew/show/P1040
虽然他在洛谷上是分类只是深度优先搜索，但比较好的做法是记忆化搜索树形DP。
树根是不确定的，因此需要枚举。我们可以定义状态dp[l][r]表示中序遍历区间为[l,r]所能得到的最大分数，利用记忆化搜索，很容易求出[1,n]的dp值；而这道题相对难实现的是给出分数最大方案的前序遍历，我们可以再开一个数组dp_root[l][r]表示[l,r]取到最大分数时选取的树根，然后跑一遍前序遍历即可。
1 #include<cstdio> 2 const int maxn=35; 3 int n,dp[maxn][maxn],dp_root[maxn][maxn]; 4 int dfs(int l,int r) { 5 if(l>r) return 1; 6 if(!dp[l][r]) 7 for(int i=l;i<=r;++i) { 8 int now=dp[i][i]+dfs(l,i-1)*dfs(i+1,r); 9 if(now>dp[l][r]) dp[l][r]=now,dp_root[l][r]=i; 10 } 11 return dp[l][r]; 12 } 13 void print(int l,int r) { 14 if(!(l==1&&r==n)) putchar(' '); 15 int rt=dp_root[l][r]; 16 printf("%d",rt); 17 if(l<=rt-1) print(l,rt-1); 18 if(rt+1<=r) print(rt+1,r); 19 } 20 int main() { 21 scanf("%d",&n); 22 for(int i=1;i<=n;++i) {scanf("%d",&dp[i][i]);dp_root[i][i]=i;} 23 int ans=dfs(1,n); 24 printf("%d ",ans); 25 print(1,n); 26 return 0; 27 }