记录编号	602695	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	Hollow07	是否通过	通过
代码语言	C++	运行时间	0.019 s
提交时间	2025-07-05 15:03:58	内存使用	3.88 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll n;
ll f[100][100],ro[100][100];

void xxs(ll l, ll r) {
	if (l>r)return;
	printf("%lld ",ro[l][r]);
	if (l==r) return;
	xxs(l,ro[l][r]-1);
	xxs(ro[l][r]+1,r);
}

int main(){
	freopen("jfecs.in","r",stdin);
	freopen("jfecs.out","w",stdout);
	scanf("%lld",&n);
	for (int i=1;i<=n;i++){
		scanf("%lld",&f[i][i]);
		f[i][i-1]=1;
		ro[i][i]=i;
	}
	for (int i=1;i<n;++i){
		for (int l=1;l<=n-i;l++){
			ll r=l+i;
			f[l][r]=f[l+1][r]+f[l][l];
			ro[l][r]=l;
			for (int k=l+1;k<r;++k) {
				if (f[l][r]<f[l][k-1]*f[k+1][r]+f[k][k]){
					f[l][r]=f[l][k-1]*f[k+1][r]+f[k][k];
					ro[l][r]=k;
				}
			}
		}
	}
	printf("%lld\n",f[1][n]);
	xxs(1,n);
	return 0;
}