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

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

int n;
int f[100][100];
int a[100];
int root[100][100];
bool t=true;
int lin;
void print(int l,int r)
{
	if(t && root[l][r]!=0)
	{
		cout<<root[l][r];
		t=false;
	}
	else if(root[l][r]!=0)
		cout<<' '<<root[l][r];
	if(root[l][root[l][r]-1]!=0)
		print(l,root[l][r]-1);
	if(root[root[l][r]+1][r]!=0)
		print(root[l][r]+1,r);		
}
	
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++)
	{
		scanf("%d",&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)
		{
			lin=INT_MIN;
			for(int k=i;k<=j;k++)
			{
				if( (f[i][k-1]*f[k+1][j]+a[k]) > lin)
				{
					lin=f[i][k-1]*f[k+1][j]+a[k];
					root[i][j]=k;
				}
			}
			f[i][j]=lin;
		}

	}	
	cout<<f[1][n]<<endl;
	print(1,n);	
	cout<<endl;
	return 0;
}