记录编号	255185	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-04-27 08:46:02	内存使用	0.31 MiB

#include <cstdio>
#include<cstring>
const int maxn = 30 + 10 ;
typedef long long ll;
inline void read(int &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
inline void read(ll &x){
	x=0;char ch;
	while(ch=getchar(),ch<'!');
	while(x=10*x+ch-'0',ch=getchar(),ch>'!');
}
ll f[maxn][maxn];
int mid[maxn][maxn];
void pre(int s,int t){
	if( s > t ) return ;
	if (s==t){printf("%d ",s) ;return ;}
	int rt = mid[s][t] ;
	printf("%d ",rt ) ;
	pre(s,rt-1) ;
	pre(rt+1,t) ;
}
int main(){
	freopen("jfecs.in" ,"r",stdin );
	freopen("jfecs.out","w",stdout);
	int n;read(n);
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++)
			f[i][j] = 1 ;
	int t;
	for(int i=1;i<=n;i++) read(f[i][i]);
	for(int l=2;l<=n;l++){
		for (int i=1;i<=n-l+1;i++){
			int j=i+l-1 ;
			for(int k=i;k<=j;k++){
				t=f[i][k-1]*f[k+1][j]+f[k][k] ;
				if (t>f[i][j]){f[i][j]=t;mid[i][j]=k;}
			}
		}
	}
	printf("%lld\n", f[1][n]) ;
	pre(1,n);
	return 0 ;
}