题解 | #加分二叉树#

import java.util.*;
public class Main{
    private static int[][]dp;
    private static int[][]dp2;//存储关于位置的dp
    public static int process(int[]grades){
        int n=grades.length;
        dp=new int[n][n];
        dp2=new int[n][n];
        //叶子结点
        for(int i=1;i<n;i++){
            dp[i][i]=grades[i];
            dp2[i][i]=i;//因为区间节点从0开头，但是实际是从1开头的下标，所以+1
        }
        //非叶子节点
        for(int i=1;i<n;i++){
            for(int j=1;j+i<n;j++){
                    dp[j][i+j]=Integer.MIN_VALUE;
                for(int k=j;k<=i+j;k++){
                    int left=k==j?1:dp[j][k-1];
                    int right=k==j+i?1:dp[k+1][j+i];
                    int score=left*right+grades[k];
                    if(score>dp[j][j+i]){
                        dp[j][j+i]=score;
                        dp2[j][j+i]=k;//因为区间节点从0开头，但是实际是从1开头的下标，所以+1
                    }
                }
            }
        }
        return dp[1][n-1];
    }
    //前序遍历递归
    public static void preOrder(int l,int r){
        if(l>r) return;
        System.out.print(dp2[l][r]+" ");
        preOrder(l,dp2[l][r]-1);
        preOrder(dp2[l][r]+1,r);
    }
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int[]grades=new int[n+1];
        for(int i=1;i<=n;i++){
            grades[i]=sc.nextInt();
        }
        System.out.println(process(grades));
        preOrder(1,n);
    }
}