思路

区间DP, 依次枚举区间长度$L$, 枚举左端点$l$, 枚举分界点$k$, 使用辅助数组记录根节点

算法设计

1. 状态定义: f[l][r]表示区间[l,r]的最高得分
2. 状态转移: f[l][r]=max(f[l][r], f[l][k-1]*f[k+1][r]+a[k])
3. 计算结果: f[1][n]

c++ 区间DP

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

const int N=35;
int n;
int w[N];
int f[N][N], g[N][N];

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

int main(){
    memset(f, 0x00, sizeof f);
    cin>>n;
    for(int i=1; i<=n; ++i) cin>>w[i];
    for(int len=1; len<=n; ++len)
        for(int l=1; l+len-1<=n; ++l){
            int r=l+len-1;
            if(l==r) {f[l][r]=w[l]; g[l][r]=l;} // 叶节点
            else{
                for(int k=l; k<=r; ++k){
                    int left=k==l?1:f[l][k-1];
                    int right=k==r?1:f[k+1][r];
                    int score=left*right+w[k];
                    if(f[l][r]<score){
                        f[l][r]=score;
                        g[l][r]=k; // g[l][r]记录区间[l,r]的根节点
                    }
                }
            }
        }
    cout<<f[1][n]<<endl;
    dfs(1, n);

    return 0;
}

python 区间DP

from typing import List
class Solution:
    def main(self, n:int , a:List[int]):
        f, g = [[0 for _ in range(n+1)] for _ in range(n+1)], [[0 for _ in range(n+1)] for _ in range(n+1)]
        def dfs(l, r):
            if l>r: return
            root=g[l][r]
            print(root+1, end=' ')
            dfs(l, root-1)
            dfs(root+1, r)

        for L in range(1, n+1):
            l=0
            while l+L-1<n:
                r=l+L-1
                if l==r: # 叶子节点
                    f[l][r], g[l][r]=a[l], l
                else:
                    for k in range(l, r+1):
                        left=1 if k==l else f[l][k-1]
                        right=1 if k==r else f[k+1][r]
                        score = left*right+a[k]
                        if f[l][r]<score:
                            f[l][r]=score
                            g[l][r]=k
                l+=1
        print(f[0][n-1])
        dfs(0, n-1)

if __name__ == '__main__':
    n=int(input())
    a=list(map(int, input().split()))
    sol=Solution()
    sol.main(n, a)