记录编号	602677	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	左清源	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2025-07-05 14:36:54	内存使用	3.90 MiB

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
const int N=35;
vector<int>G[N];
int f[N][N],g[N][N],a[N],n;
int dfs(int l,int r){
	if(f[l][r]!=-1)return f[l][r];
	if(l>r){
		f[l][r]=1;
	}else if(l==r){
		f[l][r]=a[l],g[l][r]=l;
	}else{
		f[l][r]=0;
		for(int i=l;i<=r;i++){
			if(dfs(l,i-1)*dfs(i+1,r)+a[i]>f[l][r]){
				f[l][r]=f[l][i-1]*f[i+1][r]+a[i];
				g[l][r]=i;
			}
		}
	}
	return f[l][r];
}
void add(int x,int y){
	G[x].push_back(y); 
}
void dfs2(int l,int r){
	if(l>=r)return;
	int x=g[l][r];
	if(x==l)add(x,g[x+1][r]),dfs2(x+1,r);
	else if(x==r)add(x,g[l][x-1]),dfs2(l,x-1);
	else{
		add(x,g[l][x-1]),add(x,g[x+1][r]);
		dfs2(l,x-1),dfs2(x+1,r);
	}
	return;
}
void dfs3(int x,int fa){
	printf("%d ",x);
	for(auto y:G[x]){
		if(y==fa)continue;
		dfs3(y,x);
	}
	return;
}
int main(){
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
	}
	memset(f,-1,sizeof(f)); 
	dfs(1,n);
	printf("%d\n",f[1][n]);
	dfs2(1,n);
	dfs3(g[1][n],0);
	return 0;
}