记录编号	256405	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-04-30 10:32:41	内存使用	0.34 MiB

#include<bits/stdc++.h>
using namespace std; 

long long f[40][40]={0};//f[i][j]从i到j的最大加分
int d[40]={0};
int b[40][40]={0};//b[i][j]:中序遍历为i~j时的最优根节点 
int path[40][40]={0};//path[i][j]:从i到j的最后一个节点 

long long GetMax(long long a, long long b)
{
	return a>b?a:b;
} 

void Path(const int& i, const int& j)
{
	if(i>j)	return;
	if(i==j){
		printf("%d ",i);
		return;
	}
	printf("%d ",path[i][j]);
	Path(i,path[i][j]-1);
	Path(path[i][j]+1,j);
}
 
int main()
{
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	int n=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%d",&d[i]);
	
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++)
			if(i>j)	f[i][j]=1;//保证乘积不会变 
	for(int i=1;i<=n;i++){
		f[i][i]=d[i];
		b[i][i]=i;
		path[i][i]=i;
	}//初始化	
	
	for(int l=2;l<=n;l++){//长度 
		for(int s=1;s<=n-l+1;s++){//起点 
			int end=s+l-1;//终点 
			for(int k=s;k<=end;k++){//断点 
				if(f[s][end]<f[s][k-1]*f[k+1][end]+d[k]){
						f[s][end]=f[s][k-1]*f[k+1][end]+d[k];//合并类区间长度从2到n
						path[s][end]=k;
					}
			}	
		}
	}//合并类动规 
	
	printf("%d\n",f[1][n]);
	Path(1,n);			
	return 0;		 	
}