题目分析

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;
const int N = 35;
int w[N];
int f[N][N] , traverse[N][N];
int n;


void dfs(int l , int r) {
    if (l > r) return;

    int k = traverse[l][r];
    cout << k << ' ';
    dfs(l,k - 1);
    dfs(k + 1 , r);
}
int main() {

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

    for (int len = 1 ; len <= n ; len ++ ) 
        for (int l = 1 ; l <= n - len + 1 ; l ++ ) {
            int r = l + len - 1;
            if (len == 1) f[l][r] = w[l] , traverse[l][r] = l; // 前序遍历 根 -> 左 -> 右
            else {
                for (int k = l ; k <= r ; k ++ ) {
                    int left = l == k ? 1 : f[l][k - 1];
                    int right = r == k ? 1 : f[k + 1][r];
                    int score = left * right + w[k];
                    if (f[l][r] < score) f[l][r] = score , traverse[l][r] = k;
                }
            }
        }
    cout << f[1][n] << endl;
    dfs(1,n);

    return 0;
}