记录编号	403579	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	zChengYuan	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2017-05-10 19:16:45	内存使用	0.32 MiB

#include <fstream>
#include <algorithm>
#include <vector>
#define maxn 31
using namespace std;
ifstream fin("jfecs.in");
ofstream fout("jfecs.out");
long f[maxn][maxn];
int node[maxn][maxn];
int di[maxn],n;
vector<int> res;
long dp(int i,int j);
void init();
void pre_order(int i,int j);
int main()
{
	init();
	fout<<dp(1,n)<<endl;
	pre_order(1,n);
	fout<<endl;
}
void init()
{
	fin>>n;
	for(int i=1;i<=n;++i)
	{
		fin>>di[i];
		node[i][i]=i;
	}
}
long dp(int i,int j)
{
	long &ans=f[i][j];
	if(ans>0)return ans;
	if(i==j)return ans=di[i];
	ans=1;
	for(int m=i;m<=j;++m)
	{
		long tmp=dp(i,m-1)*dp(m+1,j)+di[m];
		if(tmp>ans)
		{
			ans=tmp;
			node[i][j]=m;
		}
	}
	return ans;
}
void pre_order(int i,int j)
{
	int m=node[i][j];
	fout<<m<<' ';
	if(i<m)pre_order(i,m-1);
	if(j>m)pre_order(m+1,j);
}