dp(动态规划)总结

2018-03-27 18:48:31


目录

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

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

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]为此情况下的合法方案数。

#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,如果两条路线取走同一个格子的数,就减去一次,这样就能求出总体最优解。

#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 来源:pb0207 重点是手动推出来原始矩阵和转移方法!!!


单调性优化

暂时没学到


斜率优化

学长blog:orz徐文博

玩具装箱

放轻松,跟玩具有关的题都很可爱

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凸壳就是用向量叉乘随便搞一下

每次从队首不断出队以找出最优决策。

没了就这些

#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

题目描述:用1*2 的矩形通过组合拼成大矩形,求拼成指定的大矩形有几种拼法。

n<=11,m<=11

解法: 轮廓线dp,状压dp

首先要熟悉位运算

首先使m<=n

把每一个节点用一个m位二进制表示,每次考虑不放,往左放,往上放的状态转移

时间复杂度O(2^m*(nm))

注意:数组不要开成2^m的,否则会很慢 具体原因我也不清楚

ac代码

#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

题目大意:同简单版,只不过数据范围变成最多5列,但是行数达到1e9

解法:状压dp

预处理出行与行之间的转移关系,用矩阵乘法加速