石子合并问题：有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（或最大）。

这是一道典型的动态规划题目。令dp[i][j]为将第i到j堆石子合并成一堆的最小代价w[i][j]为第i到j堆石子的总数。就可以写出状态转移方程：

直接暴力求解就可以，复杂度O(n3)。

改进方法是用平行四边形不等式优化，缩小k的范围，复杂度O(n2) :算法学习笔记(79): 四边形不等式优化DP - 知乎 (zhihu.com)

问题的变种是让石子环形排列，即第一堆和最后一堆看成是相邻的。解决方法是在n堆石子后面再加上与前面一样的n堆石子，这样最后一堆和第一堆就相邻了。把总堆数看成2n，用上面的方法解出来就可以了。最后还需要遍历一下dp数组，求出2n堆石子里面结果最小的n堆石子作为最终结果。

P1880 [NOI1995] 石子合并 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <algorithm>
#include <iostream>
#include <vector>
#define INF 0x7fffffff
using namespace std;
int main() {
  int n;
  cin >> n;
  vector<int> stones(2 * n + 1);
  vector<vector<int>> dp(2 * n + 1, vector<int>(2 * n + 1));
  vector<vector<int>> s(2 * n + 1, vector<int>(2 * n + 1));
  vector<vector<int>> dp1(2 * n + 1, vector<int>(2 * n + 1));
  vector<int> sum(2 * n + 1, 0);
  for (int i = 1; i <= n; i++) {
    cin >> stones[i];
    stones[n + i] = stones[i];
    sum[i] = sum[i - 1] + stones[i];
  }
  for (int i = n + 1; i <= 2 * n; i++) {
    sum[i] = sum[i - 1] + stones[i];
  }

  for (int r = 0; r < 2 * n; r++) {
    for (int i = 1; i <= 2 * n; i++) {
      int j = i + r;
      if (j > 2 * n) break;
      if (i == j) {
        dp[i][i] = 0, dp1[i][i] = 0, s[i][i] = i;
        continue;
      }
      dp[i][j] = INF;
      dp1[i][j] = 0;
      for (int k = s[i][j - 1]; k <= min(j - 1, s[i + 1][j]); k++) {
        if (dp[i][j] > dp[i][k] + dp[k + 1][j]) {
          dp[i][j] = dp[i][k] + dp[k + 1][j];
          s[i][j] = k;
        }
      }
      for (int k = i; k < j; k++) {
        dp1[i][j] = max(dp1[i][j], dp1[i][k] + dp1[k + 1][j]);
      }
      dp[i][j] += (sum[j] - sum[i - 1]);
      dp1[i][j] += (sum[j] - sum[i - 1]);
    }
  }
  int re1 = INF;
  int re2 = 0;
  for (int i = 1; i <= n; i++) {
    re1 = min(re1, dp[i][i + n - 1]);
    re2 = max(re2, dp1[i][i + n - 1]);
  }
  printf("%d\n%d", re1, re2);
}