package Acwing算法练习.第五章dp;

import java.util.Arrays;
import java.util.Scanner;
//f[i,j]: 所有起点为i，终点为j的方案的最小值
//状态划分：
//按照最后一步的位置进行划分
//区间dp的特征是枚举区间长度,
public class 石子合并区间dp {
    static int N = 310;
    static int[][] f = new int[N][N];//f[i][j]表示从第i堆到第j堆的石子的合并方案
    static int[] w = new int[N];
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for(int i=1;i<=n;i++)
        {
            w[i] = sc.nextInt();
            w[i] +=w[i-1];//前缀和
        }

        for(int len=2;len<=n;len++)//枚举区间长度,区间dp的特征
        {
            for(int l=1;l+len-1<=n;l++)//左边,l+len要减1是因为右边最少留一堆
            {
                int r = l+len-1;
                f[l][r] = Integer.MAX_VALUE;
                for(int k=l;k<r;k++)//k把子区间分为两堆f[l][k],f[k+1][r]
                {
                    f[l][r] = Math.min(f[l][r],f[l][k]+f[k+1][r]+w[r]-w[l-1]);
                    //把这左右两堆合并成1堆的最小代价为:合成左堆本身需要最小代价 + 合成右堆本身需要最小代价 + 再这两堆合成在一起的代价
                }
            }
        }
        System.out.println(f[1][n]);
    }
}