记录编号	602775	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	秋_Water	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2025-07-05 16:52:10	内存使用	3.70 MiB

#include <bits/stdc++.h>
using namespace std;
const int N=38;
int n,a[N];
int f[N][N],g[N][N];
void dfs(int l,int r){
	if(l>r) return;
	int k=g[l][r];
	cout<<k<<" ";
	dfs(l,k-1);
	dfs(k+1,r);
}
int main(){
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		f[i][i]=a[i];
		g[i][i]=i;
	}
	for(int len=2;len<=n;len++){
		for(int l=1;l+len-1<=n;l++){
			int r=l+len-1;
			f[l][r]=0;
			for(int k=l;k<=r;k++){
				int sum;
				if(k==l) 
					sum=f[k+1][r]+a[k];
				else if(k==r) 
					sum=f[l][k-1]+a[k];
				else 
					sum=f[l][k-1]*f[k+1][r]+a[k];
				if(sum>f[l][r]){
					f[l][r]=sum;
					g[l][r]=k;
				}
			}
		}
	}
	cout<<f[1][n]<<"\n";
	dfs(1,n);

	return 0;
}