首页 > 代码库 > 四边形不等式优化DP——石子合并问题 学习笔记
四边形不等式优化DP——石子合并问题 学习笔记
好方啊马上就要区域赛了连DP都不会QAQ
毛子青《动态规划算法的优化技巧》论文里面提到了一类问题：石子合并。
n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。
求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。
设m[i,j]表示合并d[i..j]所得到的最小得分。
状态转移方程： 
总的时间复杂度为O(n3）。
【优化方案】
四边形不等式：
m[i,j]满足四边形不等式
令s[i,j]=max{k | m[i,j]=m[i,k-1]+m[k,j]+w[i,j] }
m[i,j]满足四边形不等式可以推出函数s[i,j]的单调性，即s[i,j]≤s[i,j+1]≤s[i+1,j+1], i≤j
优化的状态转移方程：
状态转移方程 m[i][j]=min{m[i][k-1]+m[k][j]}+w[i][j]} (i<=k<=j)
如果w同时满足四边形不等式和区间单调关系，则m也满足四边形不等式
四边形不等式优化的作用：m满足四边形不等式 -> k最优决策单调性
参考博客：http://blog.csdn.net/bnmjmz/article/details/41308919
#include <string.h>#include <iostream>#include <list>#include <map>#include <set>#include <stack>#include <string>#include <utility>#include <vector>#include <cstdio>#include <algorithm>#include <cmath>#include <queue>#define LL long long#define MOD 1000000007using namespace std;const int INF = 0x3f3f3f;const int N = 1005;int m[N][N]; //m[i,j]表示合并d[i..j]所得到的最小得分int s[N][N]; //s[i,j]记录合并方案int sum[N]; //前i个石子堆石子数量和int n;int solve(){ for(int i=1; i<=n; i++) { m[i][i] = 0; //边界条件 s[i][i] = i; } for(int l=1; l<n; l++) //枚举 l = j‘ - i { for(int i=1; i+l<=n; i++) { int j = i+l; int tmp = INF; int k = 0; for(int div=s[i][j-1]; div<=s[i+1][j];div++) //最优决策的单调性 { if(tmp > m[i][div] + m[div+1][j] + sum[j] - sum[i-1] ) { tmp = m[i][div] + m[div+1][j] + sum[j] - sum[i-1]; k = div; } } m[i][j] = tmp; s[i][j] = k; } } return m[1][n];}int main(){ while(scanf("%d",&n)!=EOF) { sum[0] = 0; for(int i=1; i<=n; i++) { int a; scanf("%d",&a); sum[i] = sum[i-1] + a; } printf("%d\n",solve()); } return 0;}
四边形不等式优化DP——石子合并问题 学习笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。