dps如何制作（三种石子合并问题）
dps如何制作（三种石子合并问题）例题1. An old Stone Game（POJ 1738）『线性相邻合并』2)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（大）。3)问题2的是在石子排列是直线情况下，现在改为环形排列求总花费最小（大）。所以本次主要攻克的目标是问题2和3。
『问题概述』
石子合并问题是经典的DP问题。首先它有如下3种题型：
1)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动任意的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成
分析：这种情况是最简单的情况，合并的是任意两堆，直接贪心即可，每次选择最小的两堆合并。本质上是使用哈夫曼树算法。
2)有N堆石子，现要将石子有序的合并成一堆，规定如下：每次只能移动相邻的2堆石子合并，合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费最小（大）。
3)问题2的是在石子排列是直线情况下，现在改为环形排列求总花费最小（大）。
所以本次主要攻克的目标是问题2和3。
『线性相邻合并』
例题1. An old Stone Game（POJ 1738）
【题目大意】
有n堆石子（1<=n<=50000）排在一行，每堆石子给定一个重量。要把n堆石子合并成一堆，每次合并只能将相邻的两堆石子合并成一堆，代价为这两堆石子的重量和，求最小的总代价。
【输出样例】
0 17 8
1.朴素的区间DP方法（O（n^3））
【分析】
题目要求的是一个最优解问题，很容易想到贪心和动态规划。但贪心有明显的错误，所以采用DP，而DP最重要的就是确定状态和找到状态转移方程。题目要求算出总体合并的最小代价，其子问题就是求出在合并的过程中每一步的最小代价。
状态：dp[i][j] - 表示从第i堆到第j堆的合并的最小代价。
那么状态如何转移呢？
通过尝试几个样例发现，每次都是相邻的两堆石子合并，而这两堆石子又是由另外的n堆石子合并而来的。那么我们可以得出一个结论，i到j堆石子最后会成为dp[i][k]和dp[k 1][j]（i < k < j）这两堆石子。
所以从 i 到 j 的最小代价就是从 i 到 k 和从 k 1 到 j 的最小代价加上最后一次合并成一堆的代价—— i 到 j 的总石子重量。可以通过枚举k来得到最小代价。
最终的到状态转移方程 ：dp[i][j]=min(dp[i][j] dp[i][k] dp[k 1][j] sum[i][j])；（i != j）。
如何枚举k也是本题的一个问题，因为没有确定 i 和 j 不好枚举 k ，所以采用的方法是枚举j - i -1。
『代码』
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n; int dp[50010][50010]; int sum[50010]; int arr[50010]; int main(){ while(scanf("%d" &n) && n != 0){ sum[0] = 0; for(int i = 1; i <= n; i ){ for(int j = i; j <= n; j ){ dp[i][j] = 2e9; } } for(int i =1; i <= n; i ){ scanf("%d" &arr[i]); sum[i] = sum[i-1] arr[i]; dp[i][i] = 0; } if(n == 1){ printf("0\n"); }else{ for(int m = 1; m < n; m ){ for(int i = 1; i <= n; i ){ int j = i m; 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]); } } } printf("%d\n" dp[1][n]); } } return 0; }
很显然dp数组的空间开了50000*50000会爆掉，并且时间复杂度到了 O（n^3） 不够高效是过不了POJ滴。
所以应该继续优化。
二、四边形不等式优化DP算法（O（n^2））
首先介绍一下算法原理：
对于（ a < b <= c< d ）如果有f[a][c] f[b][d]<=f[b][c] f[a][d]
(可以理解为一句话，交叉小于包含，即交叉的两个区间，a到c和b到d的值满足小于等于包含的两个区间[bc包含于ad])
则说这个东西满足四边形不等式，当然这个东西可能是dp数组，也可以是其他数组，比如之前提到的sum数组，表示的是i到j的花费）
给出两个定理：
1、如果上述的sum函数同时满足区间包含单调性和四边形不等式性质，那么函数dp也满足四边形不等式性质
我们再定义s(i j)表示 dp(i j) 取得最优值时对应的下标（即 i≤k≤j 时，k 处的 dp 值最大，则 s(i j)=k此时有如下定理
2、假如dp(i j)满足四边形不等式，那么s(i j)单调，即 s(i j)≤s(i j 1)≤s(i 1 j 1) 。
（证明及定理来自博主NOIAu： ）
以下为Copy过来的证明过程（如果看不下可直接跳过）：
合并石子问题
现在有n堆石子，要将石子按一定顺序地合成一堆，规定如下，每次只能移动相邻的两堆石子，合并费用为新和成一堆石子的数量，求把n堆石子全部合并到一起所花的最少或者最大花费
很容易想到这样一个dp转移
dp[i][j]=min{dp[i][k] dp[k 1][j]} cost[i][j]
震惊！这不就是之前所讲的模型嘛？原来之前O（n^3）方的合并石子问题还可以优化（我太弱了）
首先明确一点，cost[i][j]表示把第i堆到第j堆的石子和到一起的最后一步的代价，显然，之前无论怎么合并，最后一步的代价都是一样的，所以我们可以先预处理出这个cost数组，他等于cnt[j]-cnt[i-1]，其中cnt数组是前缀和
for一遍i，for一遍j，每算一次dp[i][j]还要for一遍k，自然是O(n^3)方，现在我们来按照规则判断是否可以用四边形优化
第一步（壹）证明cost为凸
对于所有的i，j，令其满足i< i 1<=j< j 1
我们需要证明
cost[i][j] cost[i 1][j 1]<=cost[i 1][j] cost[i][j 1]
移项
cost[i][j]-cost[i 1][j]<=cost[i][j 1]-cost[i 1][j 1]
令f（j）=cost[i][j]-cost[i 1][j]
f（j）=cnt[j]-cnt[i-1]-(cnt[j]-cnt[i])
f（j）=cnt[i]-cnt[i-1]
都跟j无关了，自然一定满足四边形不等式（这个时候是直接等于了，但没有违反四边形不等式）
第二步（贰）证明dp为凸
要推导dp[i][j]的凸性，自然要满足对任意的i，j，令i< i 1<=j< j 1
有如下结论
dp[i][j] dp[i 1][j 1]<=dp[i 1][j] dp[i][j 1]
令dp[i 1][j]取得最优值的时候k=x
令dp[i][j 1]取得最优值的时候k=y
令x < =y(之后还要令x > y，这里不再赘述，读者如有兴趣可以自行推导，方式相似)
将k=x代入dp[i][j]，k=y代入dp[i 1][j 1]
左式=dp[i][x] dp[x 1][j] cost[i][j] dp[i 1][y] dp[y 1][j 1] cost[i 1][j 1]①
而对于i< i 1<=j< j 1
由于已经在壹中证明了cost的凸性，所以
cost[i][j] cost[i 1][j 1]<=cost[i 1][j] cost[i][j 1]②
我们会发现这个不等式的左边在①式中出现过，所以把②式中的左式和右式替换一下可以得到如下结论
dp[i][x] dp[x 1][j] cost[i][j] dp[i 1][y] dp[y 1][j 1] cost[i 1][j 1]
<=
dp[i][x] dp[x 1][j 1] cost[i][j 1] dp[i 1][y] dp[y 1][j] cost[i 1][j]
即dp[i][j] dp[i 1][j 1]<=dp[i][j 1] dp[i 1][j]
证毕
第三步（叁）证明决策单调
现在我们已经证明了cost数组和dp数组的凸性，要证明决策单调以证明优化的正确性
即要证明s[i][j-1]<=s[i][j]<=s[i 1][j]
对于s[i][j-1]<=s[i][j]
令dp[i][j-1]取得最小值时的k=y，对于所有x≠y，令x<=y
可以有如下推导
∵x 1<=y 1<=j-1< j
四边形不等式有：
dp[x 1][j-1] dp[y 1][j]<=dp[y 1][j-1] dp[x 1][j]
在式子两边同时加上dp[i][x] cost[i][j-1] dp[i][y] cost[i][j] 可以得到
dp[i][x] dp[x 1][j-1] cost[i][j-1] dp[i][y] dp[y 1][j] cost[i][j]
<=
dp[i][x] dp[x 1][j] cost[i][j] dp[i][y] dp[y 1][j-1] cost[i][j-1]
dp[i][j-1] dp[i][j]<=dp[i][j] dp[i][j-1]
(k=x)…………(k=y)……(k=x)……(k=y)
移项
dp[i][j-1]-dp[i][j-1]<=dp[i][j]-dp[i][j]
(k=x)…………(k=y)……(k=x)……(k=y)
由于我们是令k=y时dp[i][j-1]取得最小值，那么dp[i][j-1] (k=x)一定大于等于dp[i][j-1] (k=y)，所以左式大于零，所以右式也大于零，所以对于dp[i][j-1]可以取到最优值的y，所有小于它的值，对于dp[i][j]来说，都没有y优，所以最优决策一定不是小于y的，如果令s[i][j]表示dp[i][j]取得最优值的时候的k值，那么一定有
s[i][j-1]<=s[i][j]
证毕
对于不等式后半部分的证明类似，读者有兴趣可以自己再证明一次
这是Copy结束的分割。
由交叉小于包含的原理得出的原理2，s(i j)≤s(i j 1)≤s(i 1 j 1)就为我们确定了k的范围，所以我们就可以大大缩小枚举k的时间从而将时间降到O（n^2）。
注意for的顺序，因为在推dp[i][j]的时候要用s[i][j-1]和s[i 1][j]所以i是倒序的，这样才能在求dp[i][j]的时候调用dp[i 1][j]的最优决策s[i 1][j]，而j是顺序的，这样才能在求dp[i][j]的时候调用dp[i][j-1]的最优决策s[i][j-1]。
『代码』
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int n; int dp[50010][50010]; int sum[50010]; int arr[50010]; int s[50010][50010]; int main() { while(scanf("%d" &n) && n != 0) { sum[0] = 0; for(int i = 1; i <= n; i ) { for(int j = i; j <= n; j ) { dp[i][j] = 2e9; } } for(int i =1; i <= n; i ) { scanf("%d" &arr[i]); sum[i] = sum[i-1] arr[i]; dp[i][i] = 0; s[i][i] = i; } if(n == 1) { printf("0\n"); } else { for(int i = n; i > 0; i--) { for(int j =i 1; j <= n; j ) { int temp = 2e9 te; for(int k = s[i][j-1] ; k <= s[i 1][j]; k ) { if(temp>dp[i][k] dp[k 1][j] sum[j]-sum[i-1]) { temp=dp[i][k] dp[k 1][j] sum[j]-sum[i-1]; te=k; } } dp[i][j] = temp; s[i][j] = te; } } printf("%d\n" dp[1][n]); } } return 0; }
时间优化下来，但依然没有解决50000*50000数组的溢出问题，所以给出最后一种方法。
三、GarsiaWachs算法
算法大意： 每次寻找最小的一个满足a[k-1]<=a[k 1]的k（方便起见假设a[0]和a[n 1]等于正无穷，但不必在代码中写出），那么我们就把a[k]与a[k-1]合并，之后向左找最大的一个满足a[j]>a[k] a[k-1]的j 把合并后的值a[k] a[k-1]插入a[j]的右边，最后的答案就是每次a[k]与a[k-1]合并的代价和。
举个例子：
以20 6 10 11 25 12 为例
红色为合并的两个权值a[k-1] 和 a[k]，绿色为合并后的权值a[k-1] a[k]，蓝色为找到的a[j]
『经典代码』
#include <iostream> #include <string.h> #include <stdio.h> using namespace std; const int N = 50005; int stone[N]; int n t ans; void combine(int k) { int tmp = stone[k] stone[k-1]; ans = tmp; for(int i=k;i<t-1;i ) stone[i] = stone[i 1]; t--; int j = 0; for(j=k-1;j>0 && stone[j-1] < tmp;j--) stone[j] = stone[j-1]; stone[j] = tmp; while(j >= 2 && stone[j] >= stone[j-2]) { int d = t - j; combine(j-1); j = t - d; } } int main() { while(scanf("%d" &n)!=EOF) { if(n == 0) break; for(int i=0;i<n;i ) scanf("%d" stone i); t = 1; ans = 0; for(int i=1;i<n;i ) { stone[t ] = stone[i]; while(t >= 3 && stone[t-3] <= stone[t-1]) combine(t-2); } while(t > 1) combine(t-1); printf("%d\n" ans); } return 0; }
『我写的蒟蒻代码』
#include <iostream> #include <cstdio> #include <cstring> #include <vector> #include <algorithm> using namespace std; int n a; vector<int> arr; int ans k res j; int main() { int len; scanf("%d" &n); arr.clear(); ans = 0; arr.push_back(2e9); for(int i =1; i <= n; i ) { scanf("%d" &a); arr.push_back(a); } arr.push_back(2e9); len = n 2; while(len > 3) { //寻找a[k-1]和a[k] for(int i =1; i <= len ; i ) { if(arr[i-1] <= arr[i 1]){ k = i; break; } } res = arr[k-1] arr[k]; //寻找到k的位置 for(int i = k-1; i >= 0; i--){ if(arr[i] > res){ j = i; break; } } arr.erase(arr.begin() k-1); arr.erase(arr.begin() k-1); arr.insert(arr.begin() j 1 res); ans = res; len = arr.size(); } printf("%d\n" ans); return 0; }
具体的算法及证明可以参见《The Art of Computer Programming》第3卷6.2.2节Algorithm G和Lemma W Lemma X Lemma Y Lemma Z。
『环形相邻排列』
NOI1995 石子合并
在一个圆形操场的四周摆放N堆石子 现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法 计算出将N堆石子合并成1堆的最小得分和最大得分.
【输入格式】：
数据的第1行试正整数N 1≤N≤100 表示有N堆石子.第2行有N个数 分别表示每堆石子的个数.
【输出格式】：
输出共2行 第1行为最小得分 第2行为最大得分.
【输入样例】
4
4 5 9 4
【输出样例】
43
54
既然改变在于排列的方式发生了改变那么就首先解决这个改变的问题，将环形排列转换成之前已经讨论过的链。
而对于环形的处理典型的方法是将环拆成链，也就是将长度扩大2倍，求链的最佳解可以通过枚举左端点，然后找到当前到右端点的最佳即可。
取最小值时dp_2[i][j]的表
从表里可以看出将环型的4 5 9 4 转换成 链式的 （从arr[2]开始，对应表的第二行） 5 9 4 4 和 （从arr[3]开始，对应表的第三行）9 4 4 5时可以获得最小权值。
『代码』
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; int arr[205]; int dp_1[205][205] dp_2[205][205]; int sum[205]; int main() { int n ans_min = 2e9 ans_max = -1 j; sum[0] = 0; scanf("%d" &n); for(int i = 1; i <= n; i ) { scanf("%d" arr i); sum[i] = sum[i-1] arr[i]; } //通过取余操作成环 for(int i = n 1; i <= 2*n; i ) { sum[i] = sum[i-1] arr[i%n]; } memset(dp_1 0 sizeof(dp_1)); memset(dp_2 0 sizeof(dp_2)); for(int m = 1; m < n; m ) { for(int i = 1; i < 2*n; i ) { j = i m; if(j >= 2*n) break; dp_2[i][j] = 2e9; for(int k = i; k < j; k ) { dp_1[i][j] = max(dp_1[i][j] dp_1[i][k] dp_1[k 1][j] sum[j]-sum[i-1]); dp_2[i][j] = min(dp_2[i][j] dp_2[i][k] dp_2[k 1][j] sum[j]-sum[i-1]); } } } for(int i = 1; i < 2*n; i ) { j = i n-1; if(j >= 2*n) break; ans_max = max(ans_max dp_1[i][j]); ans_min = min(ans_min dp_2[i][j]); } cout<<ans_min<<"\n"; // for(int i = 1 ; i< 2*n; i ) { // for(int j = 1; j < 2*n ; j ) { // printf("%d \t" dp_2[i][j]); // } // printf("\n"); // } // cout<<"\n"; cout<<ans_max; // for(int i = 1 ; i< 2*n; i ) { // for(int j = 1; j < 2*n ; j ) { // printf("%d \t" dp_1[i][j]); // } // printf("\n"); // } return 0; }
END.
