环形石子合并
将 $n$ 堆石子绕圆形操场排放，现要将石子有序地合并成一堆。
规定每次只能选相邻的两堆合并成新的一堆，并将新的一堆的石子数记做该次合并的得分。
请编写一个程序，读入堆数 $n$ 及每堆的石子数，并进行如下计算：
- 选择一种合并石子的方案，使得做 $n−1$ 次合并得分总和最大。
- 选择一种合并石子的方案，使得做 $n−1$ 次合并得分总和最小。
输入格式
第一行包含整数 $n$，表示共有 $n$ 堆石子。
第二行包含 $n$ 个整数，分别表示每堆石子的数量。
输出格式
输出共两行：
第一行为合并得分总和最小值，
第二行为合并得分总和最大值。
数据范围
$1\leq n \leq 200$
输入样例：
4 4 5 9 4
输出样例：
43 54
解题思路
这题与石子合并差不多一样，只是这题变成了环，需要破环成链。
比如说有$4$堆石子，那么除了将 1 2 3 4 合并成一堆石子这种合并方式外，还可以是 2 3 4 1 ， 3 4 1 2 ， 4 1 2 3 。为了能把环变成区间来求解，就需要破环成链。一个朴素的想法是枚举每一个缺口（因为有$n$堆石子，因此需要合并$n-1$次，每次合并意味着在两个不连通的点之间连一条线，$n$个点最后有$n-1$条边，因此存在一个缺口，拉开就成一条链了），此时就得到一个区间，可以做区间dp。但这种做法的时间复杂度为$O(n^4)$。
一共有$n$种缺口，意味着有$n$种不同的链。问题的本质是求$n$个长度为$n$的链的区间dp。因此可以在长度为$n$的区间的后面再接一个长度为$n$的区间，这样区间的长度就变成的$2n$，$n$个长度为$n$的链都在这个长度为$2n$的区间上。
因此可以在这个长度为$2n$的链上做区间dp，时间复杂度就变成$O(n^3)$。
AC代码如下：
1 #include <bits/stdc++.h>
2 using namespace std;
3
4 const int N = 410;
5
6 int s[N];
7 int f[N][N], g[N][N];
8
9 int main() {
10 int n;
11 scanf("%d", &n);
12 for (int i = 1; i <= n; i++) {
13 scanf("%d", s + i);
14 s[i + n] = s[i]; // 扩展为2倍的长度
15 }
16 for (int i = 1; i <= n << 1; i++) {
17 s[i] += s[i - 1]; // 求前缀和
18 }
19
20 memset(f, 0x3f, sizeof(f));
21 memset(g, -0x3f, sizeof(g));
22 for (int len = 1; len <= n; len++) {
23 for (int i = 1; i + len - 1 <= n << 1; i++) {
24 int j = i + len - 1;
25 if (len == 1) {
26 f[i][j] = g[i][j] = 0;
27 }
28 else {
29 for (int k = i; k < j; k++) {
30 f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
31 g[i][j] = max(g[i][j], g[i][k] + g[k + 1][j] + s[j] - s[i - 1]);
32 }
33 }
34 }
35 }
36
37 int minv = 2e9, maxv = -2e9;
38 for (int i = 1; i <= n; i++) { // 枚举所有长度为n的区间，一共有n个
39 minv = min(minv, f[i][i + n - 1]);
40 maxv = max(maxv, g[i][i + n - 1]);
41 }
42 printf("%d\n%d", minv, maxv);
43
44 return 0;
45 }
参考资料
AcWing 1068. 环形石子合并（算法提高课）：https://www.acwing.com/video/407/
标签：得分,int,石子,合并,环形,区间,长度 From： https://www.cnblogs.com/onlyblues/p/16651202.html