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

int a[35], dp[35][35], g[35][35];
void dfs(int i, int j){
	if(i > j) return;
	cout << g[i][j] << " ";
	dfs(i, g[i][j]-1);
	dfs(g[i][j]+1, j);
}
int main(){
	int n;
	cin >> n;
	for(int i=1;i <= n;i++){
		cin >> a[i];
	}
	for(int i=1;i <= n;i++){
		dp[i][i]=a[i];
		g[i][i]=i;
	}
	for(int len=2;len <= n;len++){
		for(int i=1;i <= n-len+1;i++){
			int j=i+len-1;
			for(int k=i;k <= j;k++){
				if(dp[i][k-1]*dp[k+1][j]+a[k] > dp[i][j]){
					dp[i][j]=dp[i][k-1]*dp[k+1][j]+a[k];
					g[i][j]=k;
				}
			}
		}
	}
	cout << dp[1][n] << "\n";
	dfs(1, n);
	return 0;
}

这段代码在输入样例时，会输出122 换行 4 2 1 3 5

这是因为在计算dp[1][2]=dp[1][0]*dp[2][2]+a[1]($k=1$)时:dp[1][0]=0（不符合题意）

导致了dp[1][2]的计算错误，所以应该在初始化中加一行dp[i][i-1]=1

这样在计算空树的时候就不会错了。