首先我们考虑二叉树中序遍历的性质:左子树->根->右子树
那么我们可以想到将原序列去掉根之后就是它的左右两棵子树的中序遍历。看到这,我们就可以考虑区间DP求值。
设用区间$i,j$表示的二叉树的最大加分为$f(i,j)$,则有$f(i,j)=max(f(i,k-1)*f(k+1,j)+a[k])$,边界值为$f(i,i)=a[i]$,然后搬套路即可
代码:(细节在注释里)
#include <bits/stdc++.h>
using namespace std;
int n,a[35];
struct it
{
int la,lb,ra,rb,rot;
long long data;
}f[35][35];//这里用结构体存加分值和左右子树的两端点
void fs(int r,int l)
{
if(r==0||l==0)
return;
cout<<f[r][l].rot<<" ";
fs(f[r][l].la,f[r][l].lb);
fs(f[r][l].ra,f[r][l].rb);
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i],f[i][i].data=a[i],f[i][i].la=0,f[i][i].lb=0,f[i][i].ra=0,f[i][i].rb=0,f[i][i].rot=i;//初始化,f(i,i)在树中必为叶子节点
//后面我一时脑抽写拧了
for(int i=n;i>=1;i--)
for(int j=i+1;j<=n;j++)
{
f[j][i].data=0;
if(f[j][i].data<f[j][i+1].data+a[i])//要字典序最小,所以从i->j枚举
{
f[j][i].data=f[j][i+1].data+a[i];
f[j][i].ra=j;
f[j][i].rb=i+1;
f[j][i].la=0;
f[j][i].lb=0;
f[j][i].rot=i;//(i,j)这棵树暂时以i为根
}
for(int k=i+1;k<j;k++)//枚举根
if(f[j][i].data<f[j][k+1].data*f[k-1][i].data+a[k])
{
f[j][i].data=f[j][k+1].data*f[k-1][i].data+a[k];
f[j][i].rot=k;//暂时将k作为根
f[j][i].la=k-1;
f[j][i].lb=i;
f[j][i].ra=j;
f[j][i].rb=k+1;
}
if(f[j][i].data<f[j-1][i].data+a[j])
{
f[j][i].data=f[j-1][i].data+a[j];
f[j][i].la=j-1;
f[j][i].lb=i;
f[j][i].ra=0;
f[j][i].rb=0;
f[j][i].rot=j;
}
}
cout<<f[n][1].data<<endl;
fs(n,1);//前序遍历:根->左->右
}