dp（动态规划）总结

# 目录 # 1. dp分类 # 2. dp优化 # 3. 一些经典问题 # 4. 补充题目 ------------ ## dp分类 ### 区间dp #### 入门题：hdu-4632 http://acm.hdu.edu.cn/showproblem.php?pid=4632 题意：求字符串有多少回文子序列。 解法： dp[i][j]表示从i到j的子序列中回文子序列的个数。 dp[i][j] = dp[i + 1][j] + dp[i][j - 1] - dp[i + 1][j - 1] 如果s[i] == s[j]，则dp[i][j] += dp[i + 1][j - 1] + 1 ```cpp scanf("%s",s); int k = strlen(s); for(int i = 0;i<k;i++) dp[i][i]=1; for(int j=0;j<k;j++){ for(int i=j-1;i>=0;i--){ dp[i][j]=(dp[i][j-1]+dp[i+1][j]-dp[i+1][j-1]+P)%P; if(s[i]==s[j]) dp[i][j]=(dp[i][j]+dp[i+1][j-1]+1)%P; } } printf("Case %d: %d\n",++cnt,dp[0][k-1]); memset(dp,0,sizeof(dp)); ``` ------------ #### POJ – 2955 http://poj.org/problem?id=2955 题意：给出一个括号字符串，问这个字符串最长合法子序列的长度。若A，B合法，则AB;（A）合法。 dp[l][r]表示区间[l,r]的最长合法子序列长度 如果s[l]==s[r]，那么dp[l][r]=dp[l+1][r-1]+2 dp[l][r]=max(dp[l][r],dp[l][k]+dp[k+1][r])，枚举断点k ```cpp if(s[1]=='e') return 0; memset(f,0,sizeof(f)); int k = strlen(s+1); for(int j = 1;j<=k;j++){ for(int i = j-1;i>=1;i--){ if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) f[i][j]=f[i+1][j-1]+2; for(int p = i+1;p<j-1;p++){ f[i][j]=max(f[i][j],f[i][p]+f[p+1][j]); } f[i][j]=max(f[i][j],max(f[i+1][j],f[i][j-1])); } } printf("%d\n",f[1][k]); ``` ------------ ### 环形dp #### 石子合并 https://www.luogu.org/problemnew/show/P1880 在一个园形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。试设计算法,计算出将N堆石子合并成1堆的最小得分和最大得分. 解法：将链复制一倍 a[i+n] = a[i] dp[i][j]表示合并i-j堆的得分。 按照j-i从小到大依次计算。 ------------ ### 状压dp 状压dp的思想是利用二进制来表示不同状态以及这些状态之间的相互转换，从而达到解决问题的目的 #### 经典问题： #### 多米诺骨牌覆盖 题目大意：有一个 n 行 m 列的矩阵，用 1*2 的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？只需求出覆盖方法总数 mod p 的值即可。m<=5 , p<=10000，1<=n<=10^9. https://www.vijos.org/p/1194 解法： F[i][j]表示填满前i-1行，第i行填充情况为j。j为第i行的二进制表示。 时间复杂度n*(2^5)*(2^5) 看到n很大，考虑使用矩阵乘法来加速。 ------------ #### noip提高组2016 愤怒的小鸟 https://www.luogu.org/problemnew/show/P2831 题目大意：用过原点的向下开口的抛物线覆盖n个坐标，n<=18。求最少需要的抛物线条数。 解法： 三点确定一条抛物线，枚举过某两个点的抛物线（原点已经确定），再统计有多少点在抛物线上（压缩为状态p[j]，在线上为1） 然后f[i]表示猪的消灭状态为i的最小步数（1表示消灭，0表示未消灭） 按照i二进制表示中1的数量从小到大更新 f[i|p[j]]=min(f[i|p[j]],f[i]+1)。 时间复杂度 (n^2)*(2^n) ------------ ### 树形dP 顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向： 1、叶－>根：在回溯的时候从叶子节点往上更新信息 2、根 - >叶：往往是在从叶往根dfs一遍之后（相当于预处理），再重新往下获取最后的答案。 不管是 从叶－>根 还是 从 根 - >叶，两者都是根据需要采用，没有好坏高低之分 例题： #### 1.(hdu1520) 给出一棵树 每个节点有权值  要求父节点和子节点不能同时取 求能够取得的最大值  #### 2.(hdu2196) 给出一棵树，求离每个节点最远的点的距离  #### 3.(poj2378) 给一个树状图，有n个点。求出，去掉哪个点，使得剩下的每个连通子图中点的数量不超过n/2。如果有很多这样的点，就按升序输出。n<=10000  #### 4.(hdu2242) 给出一些点，有值，给出一些边，然后求去掉一条边后将分成连通的两部分，且两部分的差值最小  ------------ ### 数位dp 顾名思义，数位dp就是在数字的位数上进行dp #### 例题： #### bzoj1026 [SCOI2009]windy数 http://www.lydsy.com/JudgeOnline/problem.php?id=1026 windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道， 在A和B之间，包括A和B，总共有多少个windy数？100%的数据，满足 1 <= A <= B <= 2000000000 解法： 转换为求解[1,A-1]和[1,B]的答案。 考虑从高位往低位填数 F[i][j][k]：填满第n-i位（1最低位）。n-i位是否和上限相同（相同j为1，否则为0），第i位数字位k。 F[i][j][k]为此情况下的合法方案数。 ```cpp #include<bits/stdc++.h> using namespace std; int f[20][2][11]; int solve(int M){ int n,a[20]={0}; int sum=0; for(n=0;M;M/=10) a[++n]=M%10; for(int k=0;k<=10;k++)f[n+1][0][k]=f[n+1][1][k]=0; f[n+1][1][10]=1; for(int i=n;i>=1;i--){ for(int k=0;k<10;k++){ f[i][0][k]=f[i][1][k]=0; for(int l=0;l<=10;l++){ if(abs(k-l)<2&&l!=10)continue; if(k==0&&l==10)continue; if(k>a[i]){ f[i][0][k]+=f[i+1][0][l]; f[i][1][k]+=0; } if(k==a[i]){ f[i][0][k]+=f[i+1][0][l]; f[i][1][k]+=f[i+1][1][l]; } if(k<a[i]){ f[i][0][k]+=f[i+1][0][l]+f[i+1][1][l]; f[i][1][k]+=0; } } if(i==1) sum+=f[i][0][k]+f[i][1][k]; } f[i][1][10]=0; f[i][0][10]=f[i+1][1][10]+f[i+1][0][10]; } return sum; } int main(){ int A,B; cin>>A>>B; cout<<solve(B)-solve(A-1)<<endl; return 0; } ``` ------------ ### 双线程dp #### 方格取数 其实挺水的一道题 https://www.luogu.org/problemnew/show/P1004 设有N*N的方格图(N<=9)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字0。如下图所示：  某人从图的左上角的A点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。 解法： ~~据说可以拿网络流做~~ 肯定会首先想到两遍dp，但是这样是错误的，为什么呢。我们思考一下，动态规划算法想要要求出的是最优的解，并且要求无后效性。那么问题来了，有可能我们第一遍dp求出最优解后，会对第二遍dp的过程造成影响，这样就不满足无后效性的要求，因为第一遍取走一些数后会对第二遍的路径选择造成影响。换句话说，我们求出的第一遍的最优解加上第二遍的最优解，可能不如两遍次优解的和。 观察数据范围不是很大（很小好不好），所以我们需要考虑双线dp，也就是四维dp，两条路线一起dp，如果两条路线取走同一个格子的数，就减去一次，这样就能求出总体最优解。 ```cpp #include<bits/stdc++.h> using namespace std; int f[10][10][10][10]; int a[10][10]; int main(){ int n,x,y,z; scanf("%d",&n); while(1){ scanf("%d%d%d",&x,&y,&z); a[x][y]=z; if(!x&&!y&&!z) break; } for(int i = 1;i<=n;i++){ for(int j = 1;j<=n;j++){ for(int k = 1;k<=n;k++){ for(int t = 1;t<=n;t++){ f[i][j][k][t]=max(max(f[i-1][j][k-1][t],f[i][j-1][k-1][t]),max(f[i-1][j][k][t-1],f[i][j-1][k][t-1]))+a[i][j]+a[k][t]; if(i==k&&t==j) f[i][j][k][t]-=a[i][j]; } } } } cout<<f[n][n][n][n]; return 0; } ``` ------------ ------------ ## dp优化 ### 矩阵乘法优化 #### 矩阵乘法入门题：摆花（CH Round30） ~~找到这个oj真心难~~ http://contest-hunter.org:83/contest/CH%20Round%20%2330%20-%20%E6%B8%85%E6%98%8E%E6%AC%A2%E4%B9%90%E8%B5%9B/%E6%91%86%E8%8A%B1  重点是手动推出来原始矩阵和转移方法！！！ ------------ ### 单调性优化 暂时没学到 ------------ ### 斜率优化 学长blog：[orz徐文博](https://www.zybuluo.com/KirinBill/note/1034895) #### 玩具装箱 ~~放轻松，跟玩具有关的题都很可爱~~ https://www.luogu.org/problemnew/show/P3195 P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小. 输入格式： 第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7 输出格式： 输出最小费用 解法： 如果玩具长度的前缀和为sum[]sum[] ，那么dp方程为： f[i]=min{f[j]+(i-j-1-L+sum[i]-sum[j])^2} ,0<=j<i. 考虑斜率优化。 进行美妙的数学变换 可以发现原方程为 f[i]=min{0<=j<i,f[j]+((i+sum[i]-L-1)-(sum[j]+j))^2} 设a[i]=i+sum[i]-L-1，b[j]=sum[j]+j ， 则f[i]=min{0<=j<i,f[j]+(a[i]-b[j])^2} 即f[i]=min{0<=j<i,f[j]+b[j]^2-2a[i]b[j]}+a[i]^2 再设X[j]=b[j]，Y[j]=f[j]+b[j]^2， ~~其实就是展开一下然后移移项对吧~~ 则可以发现a[] 和X[] 都单调递增，所以斜率是单调递减的。 ~~直线的斜率初中就学过~~ 用单调队列维护凸壳 ~~emmm凸壳就是用向量叉乘随便搞一下~~ 每次从队首不断出队以找出最优决策。 ~~没了就这些~~ ```cpp #include <cstdio> const int MAXN=50005; int n,l; long long k[MAXN],dp[MAXN]; inline long long sqr(register long long x){return x*x;} //intercept inline long long y_itcpt(int i){ return sqr(k[i])+(l*k[i]<<1)+dp[i]; } inline long long slope(int i){return -(k[i]<<1);} inline long long cal(int i,int j){ return slope(j)*k[i]+y_itcpt(j); } //intersection inline double itsct(int i,int j){ return (double)(y_itcpt(j)-y_itcpt(i))/(slope(i)-slope(j)); } inline long long slopeDP(){ static int dq[MAXN]; int head=0,tail=0; for(int i=1;i<=n;++i){ while(head<tail && cal(i,dq[head])>=cal(i,dq[head+1])) ++head; dp[i]=cal(i,dq[head])+sqr(k[i]-l); while(head<tail && itsct(i,dq[tail-1])<=itsct(dq[tail],dq[tail-1])) --tail; dq[++tail]=i; } return dp[n]; } int main(){ scanf("%d%d",&n,&l); ++l; for(int i=1;i<=n;++i){ scanf("%d",&k[i]); k[i]+=k[i-1]; } for(int i=1;i<=n;++i) k[i]+=i; printf("%lld",slopeDP()); return 0; } ``` ------------ ------------ ## 一些经典问题 ### 背包问题 https://blog.csdn.net/stack_queue/article/details/53544109 ------------ ### 最长上升子序列 存在n方算法和nlogn算法 nlogn算法利用库函数进行二分查找从而加速 若相邻两个数可以相等，则用lower_bound，若不可以相等，则用upper_bound 定理：最少链划分数等于最长反链长度 #### 洛谷P1020 导弹拦截 https://www.luogu.org/problemnew/show/P1020 解法：如果你知道上述定理，这就是个裸题，两遍LIS切 ------------ ### 最长公共子序列 #### 模板： https://www.luogu.org/problemnew/show/P1439 若两个串长n!=m 则只能用O(nm)的算法 a[i]==b[j]?dp[i][j]=dp[i-1][j-1]+1:dp[i][j]=max(dp[i-1][j],dp[i][j-1])； 如果是两个长度相等的串，则考虑将LCS转化为LIS 我们考虑将第一个串置换，法则就是a[i]->i 那么我们按照这个法则将第二个串置换出来，这样的话，求两者的LCS，就等价于在此置换法则下求第二个串的LIS。于是我们就得到了O(nlogn)的做法，求一下LIS就OK了。 ------------ ------------ ## 补充题目： #### 1.多米诺覆盖问题 ##### 简单版 [poj2411](http://poj.org/problem?id=2411) 题目描述：用1*2 的矩形通过组合拼成大矩形，求拼成指定的大矩形有几种拼法。 n<=11,m<=11 解法： 轮廓线dp，状压dp 首先要熟悉位运算 首先使m<=n 把每一个节点用一个m位二进制表示，每次考虑不放，往左放，往上放的状态转移 时间复杂度O(2^m*(nm)) 注意：数组不要开成2^m的，否则会很慢 ~~具体原因我也不清楚~~ ac代码 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=12; int n,m,cur; long long dp[3][(1<<maxn)+3]; inline void update(int a,int b){ if(b&(1<<m)) dp[cur][b^(1<<m)]+=dp[cur^1][a]; } int main(){ while(scanf("%d%d",&n,&m)){ if(!n){ if(!m) return 0; } if(n<m) swap(n,m); cur=0; dp[0][(1<<m)-1]=1; for(int i = 0;i<n;i++){ for(int j = 0;j<m;j++){ cur^=1; memset(dp[cur],0,sizeof(dp[cur])); for(int k = 0;k<(1<<m);k++){ update(k,k<<1); if(i && !(k&(1<<m-1))) update(k,(k<<1)^(1<<m)^1); if(j && !(k&1)) update(k,(k<<1)^3); } } } printf("%lld\n",dp[cur][(1<<m)-1]); } } ``` ##### 升级版 [voj1194](https://www.vijos.org/p/1194) 题目大意：同简单版，只不过数据范围变成最多5列，但是行数达到1e9 解法：状压dp 预处理出行与行之间的转移关系，用矩阵乘法加速