记录编号	154811	评测结果	AAAAAAA
题目名称	[NOIP 2003]加分二叉树	最终得分	100
用户昵称	落尘	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-03-25 10:36:14	内存使用	0.32 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
 
int n;
int score[31];
int root[31][31];
int dp[31][31];
 
void Input()
{
	int i;
 	cin >> n;
 	for (i = 1; i <= n; i ++)
  		cin >> score[i];
}
 
void Init()
{
 	int i;
 	memset(dp,0,sizeof(dp));
 	for (i = 1; i <= n; i ++)
 	{
  		dp[i][i] = score[i];
  		root[i][i] = i;
 	}
 	for (i = 1; i <= n - 1; i ++)
 	{
  		dp[i][i + 1] = score[i] + score[i + 1];
  		root[i][i + 1] = i;
 	}
}
 
void Dp()
{
 	int i,j,d;
 	for (d = 2; d <= n - 1; d ++)
 	{
  		for (i = 1; i <= n - d; i ++)
  		{
   			int temp;
   			dp[i][i + d] = dp[i][i] + dp[i + 1][i + d] * 1;
   			root[i][i + d] = i;
   			for (j = i + 1; j <= i + d - 1; j ++)
   			{
    			temp = dp[j][j] + dp[i][j - 1] * dp[j + 1][i + d];
    			if (temp > dp[i][i + d])
    			{
     				dp[i][i + d] = temp;
     				root[i][i + d] = j;
    			}
   			}
   			if (dp[i + d][i + d] + dp[i][i + d -1] * 1 > dp[i][i + d])//将i + d作为根节点，i到i+d-1作为左子树
   			{
    			dp[i][i + d] = dp[i + d][i + d] + dp[i][i + d -1] * 1;
    			root[i][i + d] = i + d;
   			}
  		}
 	}
}
 
void PreOrder(int x1,int x2)
{
 	if (x1 <= x2)
 	{
  		cout << root[x1][x2] << " ";
  		PreOrder(x1,root[x1][x2] - 1);
  		PreOrder(root[x1][x2] + 1,x2);
 	}
}
int main(void)
{
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	
 	Input();
 	Init();
 	Dp();
 	cout << dp[1][n] << endl;
 	PreOrder(1,n);
 	
 	fclose(stdin);
	fclose(stdout); 
 	return 0;
}