题目描述

blablabla

样例

blablabla

算法1

$O(n^3)$

Java 代码

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

public class Main{
    private static int N, M;
    private static int[][] f;
    private static int[] s;
    static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
    public static void main(String[] args) throws IOException{
        String[] s1 = read.readLine().split("\\s+");
        N = Integer.parseInt(s1[0]);
        f = new int[N+1][N+1];  
        s = new int[N+1];
        String[] str = read.readLine().split("\\s+");
        for(int i = 1; i <= N; i++){
            s[i] = Integer.parseInt(str[i-1]);
        }

        for(int i = 1; i <= N; i++){
            s[i] += s[i-1];
        }

        // 区间长度来枚举
        for(int len = 2; len <= N; len++){
            // 枚举起点
            for(int i = 1; i + len - 1 <= N; i++){
                int l = i;
                int r = i + len - 1;
                f[l][r] = Integer.MAX_VALUE;
                // 枚举分界点
                for(int k = l; k < r; k++){
                    f[l][r] = Math.min(f[l][r], f[l][k] + f[k+1][r]+ s[r] - s[l-1]);
                }

            }
        }

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

}