记录编号	167488	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-06-25 18:17:04	内存使用	0.32 MiB

#include<cstdio>
#include<deque>
#include<algorithm>
#include<iostream>
using namespace std;
int val[31],n;
int dp[31][31]={0};//将i~j当做一棵树，最大的加分
int dp2[31][31];//区间i~j以谁为根最大
int dfs(int l,int r)
{
	if(r<l) return 1;
	if(dp[l][r]>0) return dp[l][r];
	for(int i=l;i<=r;i++)
	{
		int now=dfs(l,i-1)*dfs(i+1,r)+val[i];
		if(now>dp[l][r])
		{
		dp[l][r]=now;	
		dp2[l][r]=i;
		}
	}
	return dp[l][r];
}
void out(int l,int r)
{
	if(r<l) return;
	printf("%d ",dp2[l][r]);
	out(l,dp2[l][r]-1);out(dp2[l][r]+1,r);
}
int main()
{
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&val[i]);
	for(int i=1;i<=n;i++)
		dp[i][i]=val[i],dp2[i][i]=i;
	printf("%d\n",dfs(1,n));
	out(1,n);
	return 0;
}