记录编号	602654	评测结果	AAAAAAA
题目名称	106.[NOIP 2003]加分二叉树	最终得分	100
用户昵称	淮淮清子	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2025-07-05 13:28:44	内存使用	3.74 MiB

#include<iostream>
using namespace std;

long long n;
long long x[35];
long long f[35][35];
long long rt[35][35];

void print(long long l, long long r){
    if(!rt[l][r]) return;
    cout << rt[l][r] << " ";
    print(l, rt[l][r] - 1);
    print(rt[l][r] + 1, r);
}

int main(){
//	freopen("jfecs.in","r",stdin);
//	freopen("jfecs.out","w",stdout);
	cin.tie(0) -> ios::sync_with_stdio(0);
	cin >> n;

	for(long long i = 1;i <= n;i ++){
		cin >> x[i];
		f[i][i] = x[i];
		rt[i][i] = i;
	}
	for(long long len = 2;len <= n;len ++){
		for(long long l = 1;l + len - 1 <= n;l ++){
			long long r = l + len - 1;
			for(long long k = l;k <= r;k ++){
				long long cnt = 0;
				if(k == l) cnt = f[k + 1][r] + x[k];
				else if(k == r) cnt = f[l][k - 1] + x[k];
				else cnt = f[l][k - 1] * f[k + 1][r] + x[k];
				if(f[l][r] < cnt){
					f[l][r] = cnt;
					rt[l][r] = k;
				}
			}
		}
	}
	cout << f[1][n] << '\n';
	print(1, n);
	return 0;
}