如题。

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll a[40],d[40][40],n,root[40][40]; 
void print(ll l,ll r){
	if(l > r) return;
	cout << root[l][r] << " ";
	if(l == r) return;
	print(l,root[l][r] - 1);
	print(root[l][r] + 1,r);
}
int main(){
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		d[i][i] = a[i];d[i][i - 1] = 1;		
		root[i][i] = i;
	}
	ll maxn = 0;
	for(int l = 2; l <= n; l++)
		for(int i = 1; i + l - 1 <= n; i++){
			int j = i + l - 1;
			d[i][j] = d[i + 1][j] + d[i][i];//这一行，为什么只需要考虑左子树为空
			root[i][j] = i; 
			for(int k = i + 1 ; k < j; k++){
				if(d[i][j] < d[i][k - 1] * d[k + 1][j] + d[k][k]){
					d[i][j] = d[i][k - 1] * d[k + 1][j] + d[k][k];
					maxn = max(maxn,d[i][j]);
					root[i][j] = k;
				}
			}
		} 
	cout << maxn << endl;
	print(1,n);
	return 0;
}