记录编号	163867	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	一個人的雨	是否通过	通过
代码语言	C++	运行时间	0.076 s
提交时间	2015-05-27 07:56:32	内存使用	11.34 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cstdlib>
using namespace std;
int opt[1200][1200],path[1200][1200],n,a[10000];

int treedp(int l,int r)
{
	if (opt[l][r]==0)
	{
		if (l>r)
		{
			opt[l][r]=1;
			path[l][r]=0;
		}
		else if (l==r)
		{
			opt[l][r]=a[l];
			path[l][r]=l;
		}
		else 
		{
			for (int k=l;k<=r;++k)
			{
				int x=treedp(l,k-1)*treedp(k+1,r)+a[k];
				if (x>opt[l][r])
				{
					opt[l][r]=x;
					path[l][r]=k;
				}
			}
		}
	}
	return opt[l][r];
}

void print(int l,int r)
{
	if (path[l][r]>0) {
	    printf("%d ",path[l][r]);
	    print(l,path[l][r]-1);
	    print(path[l][r]+1,r);
	}
	return;
}

int main()
{
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	scanf("%d",&n);
	for (int i=1;i<=n;++i)
	 scanf("%d",&a[i]);
	memset(opt,0,sizeof(opt));
	memset(path,0,sizeof(path));
	printf("%d\n",treedp(1,n));
	print(1,n);
	return 0;
}