$f(i,j)$表示“把区间$[i,j]$合并成一堆的选法集合”，属性：代价$Min$
对于每一个长度大于1的区间，可视为左右两堆合并而成，以$k$为分界，两区间可表示为$[i,k]$、$[k+1,j]$
状态计算：$f(i,j) = min(f(i,j), f(i,k) + f(k+1,j) + \sum^{x=j}_{x=i}a_x)$

先枚举长度，长度为1的区间不需要再合并，代价为0，所以直接从2开始枚举
再枚举起点，从1到最后一个长度的区间起点，即最后一个区间终点不能越界（$start-len+1 \leq n$）
最后枚举区间分界点，注意保证划分区间为两段（$[i,k]$、$[k+1, j]$，其中 $i \leq k \leq j-1$）

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

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

    public static void main(String[] args) throws Exception {
        int n = scanner.nextInt();
        int[] s = new int[310];  // 前缀和
        int[][] f = new int[310][310];

        for (int i = 1; i <= n; i++) {
            s[i] = scanner.nextInt();
            s[i] += s[i - 1];
        }

        // 先枚举区间长度 从小到大 先算出短区间的f 确保后面长区间划分子区间用到的f是已经算出来的
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;
                f[i][j] = Integer.MAX_VALUE;
                // 区间 [i, k] [k+1, j]
                for (int k = i; k < j; k++) {
                    // f[i][k] f[k+1][j] 是要得到这两个区间各自所要付出的代价
                    // s[j] - s[i-1] 是将上述两个区间合并成一个 所要付出的代价
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                }
            }
        }

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