记录编号	464820	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	JustWB	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-10-26 10:36:37	内存使用	0.33 MiB

#include<cstdio>
#include<iostream>
const int maxn=31;
using namespace std;
inline int get();
void print(long long l,long long r);
long long dfs(long long l,long long r);
int n;
int N[maxn];
long long root[maxn][maxn],dp[maxn][maxn];
int main()
{
    freopen("jfecs.in","r",stdin);
    freopen("jfecs.out","w",stdout);
	n=get();
	for(int i=1;i<=n;i++)dp[i][i]=N[i]=get(),root[i][i]=i;
	printf("%lld\n",dfs(1,n));
	print(1,n);
	return 0;
}
void print(long long l,long long r)
{
	if(r<l)return;
	printf("%lld ",root[l][r]);
	print(l,root[l][r]-1);
	print(root[l][r]+1,r);
}
long long dfs(long long l,long long r)
{
	if(r<l)return 1;
	if(dp[l][r])return dp[l][r];
	dp[l][r]=-1;
	register unsigned temp=1;
	for(unsigned i=l;i<=r;i++)
	{
		if(dp[l][r]<(temp=dfs(l,i-1)*dfs(i+1,r)+N[i]))
		{
			dp[l][r]=temp;
			root[l][r]=i;
		}
	}
	return dp[l][r];
}
inline int get()
{
	int t=0;char c=getchar(),j=1;
	while(!isdigit(c))
		if(c=='-')j=-1,c=getchar();
		else c=getchar();
	while(isdigit(c))
		t=(t<<3)+(t<<1)+c-'0',
		c=getchar();
	return j*t;
}