记录编号	165352	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2015-06-11 09:09:59	内存使用	0.33 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int n,a[35],f[35][35],qian[35][35];
void da(int h,int y)
{
	if(h>y) return;
	cout<<qian[h][y]<<" ";//输出主根；
	da(h,qian[h][y]-1);//左子树；
	da(qian[h][y]+1,y);//右子树；
}
int main()
{   freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		cin>>a[i];
	}
	for(int i=0;i<=n;++i)
	 for(int j=0;j<=n;++j)
	  if(i==j)
	  {
			{
				f[i][j]=a[i];
				qian[i][j]=i;
			}
	  }
	  else
	   if(i>j)
		{
			f[i][j]=1;
			qian[i][j]=0;
		}
	for(int i=n;i>=1;--i)
	 for(int j=i+1;j<=n;++j)
	 {
	    for(int k=i;k<=j;++k)
	     {if(f[i][j]<f[i][k-1]*f[k+1][j]+a[k])
		    {
				f[i][j]=f[i][k-1]*f[k+1][j]+a[k];
				qian[i][j]=k;
		    }
	    }
	 }
   cout<<f[1][n]<<endl;
   /*for(int i=1;i<=n;++i)
	for(int j=1;j<=n;++j)
	 cout<<i<<" "<<j<<" "<<qian[i][j]<<endl;*/
   da(1,n);
   //system("pause");
   
}