题目描述

blablabla

样例

blablabla

算法

Java 代码

static int[][] f;
static final int INF = 0x3f3f3f;
public static void main(String[] args) throws Exception{
    int N = nextInt();
    int[] T = new int[N+1];
    int[] s = new int[N+1];
    for(int i=1; i<=N; i++) {
       T[i] = nextInt();
       s[i] = s[i-1] + T[i];
    }
    f = new int[N+1][N+1];
    for(int l=1; l<N ;l++){
        for(int j=1; j<=N-l; j++){//枚举长度为l的每个区间
            //f[j][j+l] = Math.min();
            int L = j; int R = j+l;
            f[L][R] = INF;
            for(int i=L; i<R; i++)//枚举选定区间内部的 最后合并位置
                f[L][R] = Math.min(f[L][R], f[L][i]+f[i+1][R]+(s[R]-s[L-1]));
        }
    }
    out.print(f[1][N]);
    out.close();
}