思路分析

区间dp：在一个区间内，通过不同的划分方式求最优解的问题都可以往区间dp上靠，求方案就是记录每步的决策，也可以通过利用最优解反推的方法求决策

C++ 代码

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

const int N = 35;

int w[N];
int dp[N][N];
int root[N][N];
int n;

void dfs(int l, int r){
    if(l <= r){
        cout << root[l][r] << " ";
        dfs(l, root[l][r]-1);
        dfs(root[l][r]+1, r);
    }
}

int main(){
    cin >> n;
    for(int i = 1;i <= n;++i)cin >> w[i];

    for(int i = 1;i <= n;++i) { dp[i][i] = w[i];  root[i][i] = i;}

    for(int len = 2;len <= n;++len)
        for(int l = 1;l + len - 1 <= n;++l){
            int r = l + len - 1;
            for(int k = l;k <= r;++k){
                int left_score = (k == l ? 1 : dp[l][k-1]);
                int right_score = (k == r ? 1 : dp[k+1][r]);
                int score = left_score * right_score + w[k]; 
                if(score > dp[l][r]){
                    dp[l][r] = score;
                    root[l][r] = k;
                }
            }
        }

    cout << dp[1][n] << endl;
    dfs(1, n);
}