记录编号	602691	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	惊世猴人	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2025-07-05 14:58:25	内存使用	3.73 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long 
int n,jl[31][31];
int dp[31][31];
vector<int>v[31];
void dfs(int l,int r){
	if(l>r)return;
	int root=jl[l][r];
	cout<<root<<' ';
	if(l==r)return;
	dfs(l,root-1);
	dfs(root+1,r);
}
signed main(){
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>dp[i][i];
		dp[i][i-1]=1;
		jl[i][i]=i;
	}
	for(int l=2;l<=n;l++){
		for(int s=1;s<=n-l+1;s++){
			int e=s+l-1;
			dp[s][e]=dp[s+1][e]+dp[s][s];
			jl[s][e]=s;
			for(int j=s+1;j<e;j++){
				if(dp[s][j-1]*dp[j+1][e]+dp[j][j]>dp[s][e]){
					dp[s][e]=dp[s][j-1]*dp[j+1][e]+dp[j][j];
					jl[s][e]=j;
				}
			}
		}
	}
	cout<<dp[1][n]<<endl;
	dfs(1,n);
	fclose(stdin);
	fclose(stdout);
	return 0;
}