记录编号	108987	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2014-07-07 14:43:58	内存使用	0.31 MiB

#include <cstdio>

#define  maxn 40

int n ;
long long f[maxn][maxn] ;
int r[maxn][maxn] = {0} ;


void pre(int s , int t )
{
	if (s > t) return ;
	if (s == t )
	{
		printf("%d ", s ) ;
		return ;
	}
	int root = r[s][t] ;
	printf("%d ", root ) ;
	pre(s , root-1) ;
	pre(root+1 , t) ;
}

int main()
{
	freopen("jfecs.in" ,"r",stdin );
	freopen("jfecs.out","w",stdout);
	scanf("%d", &n ) ;
	for (int i = 0 ; i <= n+1 ; i ++ )
		for (int j = 0 ; j <= n+1 ; j ++ )
			f[i][j] = 1 ;
	for (int i = 1 ; i <= n ; i ++ )
	{
		scanf("%lld", &f[i][i] ) ;
	}
	
	//dp
	for (int d = 2 ; d <= n ; d ++ )
	{
		for (int i = 1 ; i <= n-d+1 ; i ++ )
		{
			int j = i+d-1 ;
			for (int k = i ; k <= j ; k ++ )
			{
				int t = f[i][k-1]*f[k+1][j]+f[k][k] ;
				if (t > f[i][j])
				{
					f[i][j] = t ;
					r[i][j] = k ;
				}
			}
		}
	}
	
	printf("%lld\n", f[1][n]) ;
	
	pre(1,n);
	return 0 ;
}