AcWing 282. 石子合并
原题链接
简单
作者:
hhu-菜菜
,
2021-05-19 21:28:03
,
所有人可见
,
阅读 191
import java.util.Scanner;
public class Main{
private static final int N = 310;
private static int n;
private static int[] s = new int[N];
private static int[][] dp = new int[N][N];
public static void main(String[] args){
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
for(int i = 1;i <= n;i++){
s[i] = reader.nextInt();
}
for(int i = 1;i <= n;i++){
s[i] += s[i-1];
}
reader.close();
for(int len = 2;len <= n;len++){
for(int i = 1;i+len-1 <= n;i++){
int l = i,r = i + len - 1;
//枚举最后一次的分界,再计算最小值的时候,先要初始化成一个最大的数
dp[l][r] = Integer.MAX_VALUE;
for(int k = l;k < r;k++){
dp[l][r] = Math.min(dp[l][r],dp[l][k]+dp[k+1][r]+s[r]-s[l-1]);
}
}
}
System.out.println(dp[1][n]);
}
}