「区间DP-步入」石子合并（环形）

石子合并（环形）

题目描述

在一个圆形操场的四周摆放 N 堆石子，现要将石子有次序地合并成一堆，规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出一个算法,计算出将 N 堆石子合并成 1 堆的最小得分和最大得分。

输入格式

数据的第 1 行是正整数 N，表示有 N 堆石子。

第 2 行有 NN 个整数，第 i 个整数 a i a_i ai​ 表示第 i 堆石子的个数。

输出格式

输出共 2 行，第 1 行为最小得分，第 2 行为最大得分。

样例

4
4 5 9 4

43
54

说明

• $1\le N\le 100$， 0 ≤ a i ≤ 20 0\\leq a_i\\leq 20 0≤ai​≤20
• https://www.luogu.com.cn/problem/P1880

解析

不会的先去看简单版的石子合并，此题在此基础上做小改动

代码

public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);final int MAX = 2 * n + 1;final int INF = 1 << 30;int n = sc.nextInt();int[] F = new int[MAX];int[][] dpMin = new int[MAX][MAX];int[][] dpMax = new int[MAX][MAX];int[] sum = new int[MAX];for(int i = 1; i <= 2 * n; i++) Arrays.fill(dpMin[i], INF);for(int i = 1; i <= n; i++) {F[i] = sc.nextInt();F[i + n] = F[i]; // 复制一遍}for(int i = 1; i <= 2 * n; i++) {sum[i] = sum[i-1] + F[i];dpMin[i][i] = 0;}for(int len = 2; len <= n; len++) {for(int i = 1; i + len - 1 <= 2 * n; i++) {int j = i + len - 1;for(int k = i; k < j; k++) {dpMin[i][j] = Math.min(dpMin[i][j], dpMin[i][k] + dpMin[k+1][j] + sum[j] - sum[i-1]);dpMax[i][j] = Math.max(dpMax[i][j], dpMax[i][k] + dpMax[k+1][j] + sum[j] - sum[i-1]);}}}int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;for(int i = 1; i <= n; i++) {min = Math.min(min, dpMin[i][i + n - 1]); // [1,n], [2,n+1], ...max = Math.max(max, dpMax[i][i + n - 1]); // [1,n], [2,n+1], ...}System.out.println(min);System.out.println(max);}
}