Ryan_<

树型dp一般用记忆化搜索实现

处理时用p[i][j]记录子树i~j的根，递归输出前序遍历即可~

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#define for1(i,n) for(int i=1;i<=(n);i++)
using namespace std;
const int M=31;
int p[M][M],f[M][M],d[M],n,ans;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
} 
int dp(int i,int j)//子树i~j最高加分值
{
	int k,maxn=0;
	if(i>j) return 1;//注意是空树
	if(i==j) return d[i]; 
	//注意是自己节点作为根节点（即叶子节点），而非空树
	if(f[i][j]>0) return f[i][j];
	//记忆化搜索的关键步骤 若之前处理过则直接返回其值
	for(int k=i;k<=j;k++)
	{
		int tmp=dp(i,k-1)*dp(k+1,j)+d[k];
		if(tmp>f[i][j])
		{
			f[i][j]=tmp;
			p[i][j]=k;//这里为了记录路径 
		}
	} 
	return f[i][j];
}
void print(int i,int j)//输出前序遍历 递归实现 
{
	if(i>j) return;
	if(i==j) {printf("%d ",i);return;}
	//叶子节点，可看做所在子树的根节点 处理完直接return 
	printf("%d ",p[i][j]);//根 
	print(i,p[i][j]-1);//左 
	print(p[i][j]+1,j);//右 
}
int main()
{
	n=read();
	for1(i,n) d[i]=read();
	ans=dp(1,n); 
	printf("%d\n",ans);
	print(1,n);
	return 0;
}