$$\color{Red}{环形石子合并 详细题解}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

题目介绍

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。

规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。

请编写一个程序，读入堆数 n 及每堆的石子数，并进行如下计算：

• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。
• 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

输入格式
第一行包含整数 n，表示共有 n 堆石子。

第二行包含 n 个整数，分别表示每堆石子的数量。

输出格式

输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

数据范围

1≤n≤200

输入样例：

4
4 5 9 4

输出样例：

43
54

1.算法细节

本题是区间DP，是石子合并的升级版，也给我们解决环形问题转化为线性问题提供了一个思路

我的石子合并题解

合并果子是选择任意两堆合并，而合并石子是只能相邻的合并，因此不能利用哈夫曼树的思路去用贪心解题

• 以什么来判断我们需要用到所谓的区间DP？

最开始我们并不知道这道题是区间DP，但我们很容易想到以dp[i][j]来表示：从第i堆到第j堆石子合并所花最小代价的状态表达式，同时属性为最小值。

• 那么如何把环转化为一个链呢？

其实我们可以这么想，把环形的石子看作一个个点，每次选取其中的两个合并相当于给两堆连一条边，那么我们发现最后一定是连n-1条边，这样我们在区间dp的基础上，可以在外面嵌套一层大循环，枚举到底缺口在哪，只需要枚举n-1次，找到缺口即确定起点和终点

但这么做，相当于本身O(n ^ 3)的区间dp问题变成了O(n ^ 4)，这道题会超时

• 那么如何优化呢？

很简单，我们可以复制一份接到最开始的数组，变成两份，如 1 2 3 2 ——》 1 2 3 2 1 2 3 2
这样我们枚举区间长度还按n来算，但是总石子多了n份，这样我们只需要从f[1][n] 枚举到f[n][n + n - 1]寻找答案
复杂度变成了O((2n) ^ 3)

• 那么如何构造我们的状态方程呢？

显然，合并操作每次最终总会划分为两堆的合并，最后化为一个表达式，这个表达式的结果可以构造为dp[i][j] = dp[i][k] + dp[k+1][j] + s[j] - s[i-1]
这么顺畅的下去，我们岂不是就化作了一个简单的动态规划，只需要两层for循环：

for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        -------

• 然后利用这个表达式，加上特判情况，岂不是就解决了问题？

当然不对

DP问题，在分析递推式最重要的，在01背包与完全背包的区分即可看出，我们首要考虑的是前一个状态
到底是不是在这个应有的循环条件下已经算出并且不会污染。

举例分析：dp[1][3] 的源头：dp[1][1] + dp[2][3]　　dp[1][2] + dp[3][3]
以我们线性DP的逻辑。只能先算出dp[1][n]才会去算dp[2][n],然而这种时候正常的线性dp就失效了

怎么样可以保证每次先把这些包含在其中一段段长度不一的表达式先算出来，还不会被污染呢？
区间DP闪亮登场

区间DP模板代码

for (int len = 1; len <= n; len++) // 先枚举区间长度算出内部作为基础
{        
    for (int i = 1; i + len - 1 <= n; i++) // 枚举起点，极限起点位置由区间长度和起点位置决定
    { 
        int j = i + len - 1;// 区间终点
        if (len == 1) {     // 区间长度为1一般可以赋初始值
            dp[i][j] = 初始值
            continue;
        }
        // 枚举分割点，构造状态转移方程 i <= k < j!
        for (int k = i; k < j; k++)    
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + w[i][j]);
    }
}

以前只是大概背下模板，但是没能理解流程，这里具体进入代码举例子：f[1][10] = max((f[1][2] + f[3][10]) + (f[1][3] + f[4][10]) .....)，我们想算f[1][10]需要先把内部的都算出来，算内部又是相同的，需要先算内部，这样我们就递归的先递归到最内部，从区间长度为1开始，把f[1][2],f[2][3]等算出，然后再去增加区间长度，算f[1][3], f[2][4]等，最后一步步就可以算长的区间了

2.具体代码

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static int N = 410;
    static int [] a = new int[N];
    static int[] s = new int[N];
    static int[][] f = new int[N][N];
    static int[][] g = new int[N][N];

    static int n;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        String[] s1 = br.readLine().split(" ");
        //两倍输入
        for (int i = 1; i <= n; i++) a[i] = a[i + n] = Integer.parseInt(s1[i - 1]);
        // 前缀和数组生成
        for (int i = 1; i <= n * 2; i++) {
            s[i] = s[i-1] + a[i];
            Arrays.fill(f[i], 0x3f3f3f3f);
            Arrays.fill(g[i], -0x3f3f3f3f);
        }
        // 区间DP
        for (int len = 1; len <= n; len++) {
            for (int i = 1; i + len - 1 <= 2 * n; i++) {
                int j = i + len - 1;
                if (len == 1) f[i][j] = g[i][j] = 0;
                else {
                    for (int k = i; k < j; k++) {
                        f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
                        g[i][j] = Math.max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
                    }
                }
            }
        }
        // 寻找断点答案
        int max_ans = -0x3f3f3f3f, min_ans = 0x3f3f3f3f;
        for (int i = 1; i <= n; i++) {
            max_ans = Math.max(max_ans, g[i][i + n - 1]);
            min_ans = Math.min(min_ans, f[i][i + n - 1]);
        }
        System.out.println(min_ans);
        System.out.println(max_ans);
    }
}