石子合并系列问题【区间dp，环形，四边不等式优化】
石子合并（一）
最基础的区间dp
有N堆石子排成一排(n<=100),现要将石子有次序地合并成一堆，规定每次只能选相邻的两堆合并成一堆，并将新的一堆的石子数，记为改次合并的得分，编一程序，由文件读入堆数n及每堆石子数(<=200)；
选择一种合并石子的方案，使得做n-1次合并，得分的总和最少/最多。
我们首先可以算出两两合并的得分， 通过两两合并的得分我们可以知道相邻三个合并的得分，然后相邻四个，五个······以此类推
举个栗子，对于 1 2 3 4 5，要把他们合并，假如我们已经知道相邻2个，3个，4个的得分，我们可以枚举两堆石子之间的断点k
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]); （sum为前缀和， dp[ i ] [ j ] 表示合并第 i 到 j 堆的最大的分）
这就是区间dp了，我们可以从小到大枚举区间长度，当然也可以枚举起点终点
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int maxn =6e3; const int inf = 0x7fffffff; int a[maxn], dp[maxn][maxn], sum[maxn], f[maxn][maxn]; int main(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); sum[i] = sum[i-1] + a[i];//维护一下前缀和便于计算得分 } for(int d=2; d<=n; d++){ //枚举区间长度 for(int i=1,j; (j=i+d-1)<=n; i++){//区间起点i， 终点j，且保证j不能超出范围 dp[i][j] = inf; //保存最小值，初始化 f[i][j] = 0; //保存最大值，初始化 for(int k=i; k<j; k++){//枚举 dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+sum[j]-sum[i-1]);//最大 f[i][j] = max(f[i][j],f[i][k]+f[k+1][j]+sum[j]-sum[i-1]);//最小 } } } printf("%d %d ", dp[1][n],f[1][n]); return 0; }
石子合并（二）
在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
比（一）多了一个条件：圆形操场
乍一想很复杂，其实我们可以把这个圆拆成一条链，链的长度为原本的二倍（也就是把（一）的一堆石子复制一下再接到后面）
然后按照（一）中的做法对这条链求长度为n的区间的最大得分，可以覆盖圆中的所有情况，也就是等效的
#include<cstdio> #include<algorithm> #include<cstring> #include<iostream> using namespace std; const int maxn =6e3; const int inf = 0x3f3f3f3f; int a[maxn], dp[maxn][maxn], sum[maxn], f[maxn][maxn]; int main(){ int n; scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); a[i+n] = a[i]; } for(int i=1; i<=n*2; i++){ sum[i] = sum[i-1] + a[i]; } int maxx = 0; int minn = inf; for(int i=2*n-1; i>=1; i--){ for(int j=i+1; j<i+n; j++){//这里我直接枚举了起点和终点 dp[i][j] = inf; for(int k=i; k<j; k++){ dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]+sum[j] - sum[i-1]); f[i][j] = max(f[i][j], f[i][k]+f[k+1][j]+sum[j] - sum[i-1]); } } } for(int i=1; i<=n; i++){ minn = min(minn, dp[i][i+n-1]);//限制区间长度n maxx = max(maxx, f[i][i+n-1]);//并求最大/最小值 } printf("%d %d ", minn, maxx); return 0; }
石子合并（三）
题目和（二）完全一致，但数据范围大得多，我们就要考虑时间复杂度了
可以用四边不等式优化，还有一种GarsiaWachs算法（强大又玄学，不会）
四边不等式
对于一个数组 f[][] , a < b <= c < d, 若它满足四边不等式，则
f[a][c]+f[b][d]<=f[b][c]+f[a][d]
设 w[ i ][ j ] 表示 i 到 j 的石子数，我们现在证明它满足四边不等式
令 b = a + k， d = c + k， 即 a < a+k <= c < c+k
我们证明 w[a][c] + w[a+k][c+k] <= w[a+k][c] + w[a][c+k];
移项，得 w[a][c] - w[a+k][c] <= w[a][c+k] = w[a+k][c+k];
问题转化成了证明函数f（j）= w[a][c] - w[a+k][c] 不递减
然后再证 f[] 满足四边不等式
我们要证明f[i][j] + f[i+1][j+1] <= f[i][j+1]+f[i+1][j]成立（i < i+1 <= j < j+1）
设 f [i][j+1] 的最优断点为 x
f [i+1][j] 的最优断点为 y
若 x <= y
设此时 f[x+1][j] + f[y+1][j+1] <=f[x+1][j+1] + f[y+1][j]
显然 f[i][j] <= f[i][x] + f[x+1][j] + w[i][j]
f[i+1][j+1] <= f[i+1][y] + f[y+1][j+1] + w[i+1][j+1]
相加得 f[i][j] + f[i+1][j+1] <= f[i][x] + f[x+1][j] + w[i][j] + f[i+1][y] + f[y+1][j+1] + w[i+1][j+1]
因为 w 满足四边不等式 w[i][j] + w[i+1][j+1] <= w[i][j+1] + w[i+1][j]
所以 f[i][x] + f[x+1][j] + w[i][j] + f[i+1][y] + f[y+1][j+1] + w[i+1][j+1]
<= f[i][x] + f[x+1][j] +w[i][j+1]+ f[i+1][y] + f[y+1][j+1] + w[i+1][j]
又因为 f[x+1][j] + f[y+1][j+1] <=f[x+1][j+1] + f[y+1][j]
所以 f[i][x] + f[x+1][j] +w[i][j+1]+ f[i+1][y] + f[y+1][j+1] + w[i+1][j]
<= f[i][x] + f[x+1][j+1] +w[i][j+1] +f[i+1][y]+ f[y+1][j] + w[i+1][j] = f[i][j+1] + f[i+1][j]
即 f[i][j] + f[i+1][j+1] <= f[i][j+1] + f[i+1][j]
我们可以把 ‘1’换成任意数，从而得证。
还没完（累死了）设 s[i][j] 表示 i 到 j 的最优分割点
证明 s[i][j-1] <= s[i][j] <= s[i+1][j]
我们令d=s[i][j-1] , k <= d
cut=x 表示以x为分割点的dp值（即dp[i][j]=dp[i][x]+dp[x+1][j]+cost[i][j]）
构造一个式子
(dp[i][j] - dp[i][j]) - (dp[i][j-1] - dp[i][j-1])
cut=k cut=d cut=k cut=d
=(dp[i][j] + dp[i][j-1]) - (dp[i][j-1] + dp[i][j])
cut=k cut=d cut=k cut=d
=(dp[i][k]+dp[k+1][j]+cost[i][j]+dp[i][d]+dp[d+1][j-1]+cost[i][j-1])-(dp[i][k]+dp[k+1][j-1]+cost[i][j-1]+dp[i][d]+dp[d+1][j]+cost[i][j] )
=(dp[k+1][j]+dp[d+1][j-1])-（dp[k+1][j-1]+dp[d+1][j]）
因为 k+1<=d+1 <=j-1< j，由四边形不等式可知
=dp[k+1][j]+dp[d+1][j-1] >= dp[k+1][j-1]+dp[d+1][j]
所以
(dp[i][j] - dp[i][j]) - (dp[i][j-1] - dp[i][j-1]) >= 0
cut=k cut=d cut=k cut=d
移一下项
(dp[i][j] - dp[i][j]) >= (dp[i][j-1] - dp[i][j-1])
cut=k cut=d cut=k cut=d
又因为d是dp[i][j-1]的最优分割点
所以
(dp[i][j-1] - dp[i][j-1]) >=0 (因为cut=d时dp[i][j-1]取最小值,cut取其他位置时得到的值必然大于在d点切割取的值)
cut=k cut=d
所以
(dp[i][j] - dp[i][j]) >=0
cut=k cut=d
又因为k是任意小于d的数（k<=d）
dp[i][j] >= dp[i][j]
cut=k cut=d
所以要想dp[i][j]最小，那么它的最优分割点s[i][j]必然大于等于d (d=s[i][j-1])
即 s[i][j] >= s[i][j-1]
证毕，同理可得
s[i][j] <= s[i+1][j]
有了s[i][j-1]<=s[i][j]<=s[i+1][j]这个结论
总结一下证明过程，就是先证明显然的w，由w证明f，由 f 证出 s
for (int i = 1; i <= n; i++) //枚举右端点-左端点的值
{
for (int j = 1; j + i <= n; j++) //枚举区间左端点
{
int e = j + i; //区间右端点
dp[j][e] = inf;
for (int k = s[j][e - 1]; k <= s[j + 1][e]; k++)
{
if (dp[j][e] > dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1])
{
dp[j][e] = dp[j][k] + dp[k + 1][e] + sum[e] - sum[j - 1];
s[j][e] = k;
}
}
}