1068 环形石子合并（环形区间dp变成链的技巧）

青旅半醒 2022-09-12 12:56 159阅读 0赞

**1. 问题描述：**

将 n 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。请编写一个程序，读入堆数n及每堆的石子数，并进行如下计算：  
选择一种合并石子的方案，使得做 n−1 次合并得分总和最大。  
选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

**输入格式**

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

**输出格式**

输出共两行：第一行为合并得分总和最小值，第二行为合并得分总和最大值。

**数据范围**

1 ≤ n ≤ 200

**输入样例：**

4  
4 5 9 4

**输出样例：**

43  
54  
来源：[https://www.acwing.com/problem/content/description/1070/][https_www.acwing.com_problem_content_description_1070]

**2. 思路分析：**

这道题目其实是[282题石子合并][282]的简单扩展，282题中n堆石子是排成一排的，也即一条链的形式，这道题目的n堆石子是围成一圈的，我们希望将当前的问题转换为上一个问题，这样就可以使用上一题的思路求解了，转换的核心是如何将当前问题中的环转换为链；其实我们可以将石子看成是一个点，如果合并相邻的石子那么我们就在这两堆石子上连上一条边，所以问题的本质其实是最终连的那条边的位置；也即可以看成给我们n个长度为n的链让我们求解合并石子的最大花费与最小花费；对于环形的问题其实有一种比较经典的做法是**将原数组复制一遍接到原数组的后面**，可以发现之前n个长度为n的链都在长度为2n的链上，这样我们就将环转化为了链，所以只需要在长度为2n的链上做一次区间dp即可，最后枚举所有长度为n的链求解出最小花费和最大花费即可。因为需要求解最小花费与最大花费所以我们需要声明两个数组来记录，f和g数组分别记录区间最大值与最小值，然后使用经典的区间dp的步骤解决即可，与282题的解决过程是一模一样的。

**3. 代码如下：**

if __name__ == '__main__':
        # 这道题目的核心是如何将环形转换为一条链
        n = int(input())
        w = list(map(int, input().split()))
        # 复制一遍数组接到原数组的后面
        for i in range(n):
            w.append(w[i])
        # 计算前缀和, 前缀和第一个元素为0
        s = [0]
        # 计算前缀和
        for i in range(2 * n):
            s.append(s[-1] + w[i])
        INF = 10 ** 9
        # f, g分别记录区间最大值与最小值
        f = [[0] * (2 * n + 1) for i in range(2 * n + 1)]
        g = [[INF] * (2 * n + 1) for i in range(2 * n + 1)]
        # 区间长度只需要枚举到n
        for l in range(1, n + 1):
            i = 1
            while i + l - 1 <= 2 * n:
                j = i + l - 1
                if l == 1:
                    f[i][j] = g[i][j] = 0
                else:
                    for k in range(i, j):
                        # 长度为1的时候不需要合并石子所以值为0
                        f[i][j] = max(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1])
                        g[i][j] = min(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1])
                i += 1
        # 枚举所有长度为n的区间
        maxv, minv = 0, INF
        for i in range(1, n + 1):
            maxv = max(maxv, f[i][i + n - 1])
            minv = min(minv, g[i][i + n - 1])
        # seq为两个元素的分割符
        print(minv, maxv, sep="\n")

[https_www.acwing.com_problem_content_description_1070]: https://www.acwing.com/problem/content/description/1070/
[282]: https://blog.csdn.net/qq_39445165/article/details/120469327