1. 区间DP步骤：先枚举区间长度，再枚举起点，从而计算终点，最后枚举区间分界点，思考当前区间与子区间的关系
2. 状态计算：$f(i,j) = max(f(i,k-1) * f(k+1, j) + w_k),\ i < k < j$
   • 区间分为三部分：左子树$w[i \cdots k-1]$、根$w_k$、右子树$w[k+1 \cdots j]$，需要考虑左右子树可能不存在情况
   • 若只有左子树没有右子树则$f(i,j)=1\*f(k+1,j) + w_k$
   • 若只有右子树没有左子树则$f(i,j)=f(i,k-1) \* 1 + w_k$
   • 若只有根没有子树则$f(i,j)=w_k$
3. 要求输出具体方案，另开数组，在更新区间分数最大值时，更新该最大值对应的分界点，最后递归推导整个方案

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;
    static int[][] f = new int[32][32], root = new int[32][32];
    static int[] a = new int[32];

    static String dfs(int l, int r) {
        if (l > r) return "";
        int t = root[l][r];
        return t + " " + dfs(l, t - 1) + dfs(t + 1, r);
    }

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) a[i] = scanner.nextInt();

        for (int len = 1; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                for (int k = i; k <= j; k++) {
                    int left = k == i ? 1 : f[i][k - 1], right = k == j ? 1 : f[k + 1][j];
                    int score = left * right + a[k];
                    if (i == j) score = a[k];
                    if (score > f[i][j]) {
                        f[i][j] = score;
                        root[i][j] = k;
                    }
                }
            }
        }

        System.out.println(f[1][n]);
        System.out.println(dfs(1, n));
    }
}