记录编号	201914	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	蜗牛哲	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-10-31 15:24:24	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<climits>
using namespace std;

const int maxn=30+2;
int a[maxn],f[maxn][maxn],root[maxn][maxn];

int n;

void front(int x,int y)
{
	if(root[x][y]!=0)
		printf("%d ",root[x][y]);
	if(root[x][root[x][y]-1]!=0) front(x,root[x][y]-1);
	if(root[root[x][y]+1][y]!=0) front(root[x][y]+1,y);
}

int main()
{
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	
	cin>>n;
	for(int i=0; i<=n; i++)
	for(int j=0; j<=n; j++)
	{
		f[i][j]=1;
	}
	for(int i=1; i<=n; i++)
	{
		cin>>a[i];
		f[i][i]=a[i];
		root[i][i]=i;
	}
	
	for(int len=1; len<=n; len++)
	for(int i=1; i<=n; i++)
	{
		int j=i+len;
		
		if(j<=n)
		{
			int max1=INT_MIN;
			for(int k=i; k<=j; k++)
			{
				if(f[i][k-1]*f[k+1][j]+a[k]>max1)
				{
					max1=f[i][k-1]*f[k+1][j]+a[k];
					root[i][j]=k;
				}
			}
			f[i][j]=max1;
		}
	}
	
	cout<<f[1][n]<<endl;
	
	front(1,n);
	
	return 0;
}