solution.java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[1010];
        int[][] dp = new int[1010][1010];
        int[][] jiaoshui = new int[1010][1010];
        // dp[i][j]代表从第i个到第j个石头合并的重量
        // jiaoshui[i][j]代表从第i个到第j个石头合并的胶水量
        for (int i = 1; i <= n; i++) {
            a[i] = in.nextInt();
            dp[i][i] = a[i];
        }
        // for (int i=1; i<n; i++) {
        // for(int j=i+1; j<=n; j++) {
        // dp[i][j]=dp[i][j-1]+a[i];
        // }
        // }
        // r是循环的范围，要从两个石头合并开始算，因为只有相邻的才能合并
        for (int r = 2; r <= n; r++) {
            // 循环起始点，j就是从i向后r个范围的点j
            for (int i = 1; i <= n - r + 1; i++) {
                int j = i + r - 1;
                jiaoshui[i][j] = Integer.MAX_VALUE;
                // 这个是代表的用的哪个范围合并的石头，最后要加起来
                int temp1 = 0;
                // 这个是取两个相邻石头差值最大的拼凑
                // 好比一共10个石头
                // 差值小：一堆分五块 5*5=25
                // 差值大： 一个1块一个9块 1*9=9
                // 胶水量形成了鲜明的对比，差值大的省胶水
                int tempmax = -1;
                for (int k = i; k < j; k++) {
                    if (tempmax < Math.abs(dp[i][k] - dp[k + 1][j])) {
                        // 保存从哪里分开(哪两堆石头合并起来的)
                        temp1 = k;
                        // dp[i][j]代表从第i个到第j个石头合并有重
                        dp[i][j] = dp[i][k] + dp[k + 1][j];
                        // 找差值最大的进行合并省胶水
                        tempmax = Math.abs(dp[i][k] - dp[k + 1][j]);
                        jiaoshui[i][j] = dp[i][k] * dp[k + 1][j];
                    }
                }
                // 如果jiaoshui[i][i]表示的是一个石头，一个石头粘连在一起是不需要胶水的，这里要跳过
                if (i != temp1)
                    jiaoshui[i][j] += jiaoshui[i][temp1];
                if (temp1 + 1 != j)
                    jiaoshui[i][j] += jiaoshui[temp1 + 1][j];
            }
        }
        // 1-n粘连需要的最小胶水
        System.out.println(jiaoshui[1][n]);
    }
}