逊哥dp专题 总结(普通dp,斜率优化dp,数位dp)

dp真是博大精深,本渣自叹智商不足,但是就算是不足也要拼死一搏,怒燃之

poj 3934

题意:给你n个身高都不同的人,然后排队,如果两人之间的所有人都比他们俩矮,那么他们俩可以互相看见,问你如果要正好让m对人能互相看见,那么有多少种方法

题解:一开始状态各种想不出啊,其实这题也不难,定义状态为dp[i][j],为前i个人,构成j对互相看见有多少种方法

考虑转移过程,i个人肯定是 从i-1个转移过来的,就等于把第i个人往i-1个人的队列里插

方便考虑,可以想成是所有人从高到低排队,先放高的人,第i个人是前i个中最矮的,如果把第i个人放在两边,就能多一对,有两边可以放,如果放在i-1个中间,就能多2对,有i-2个地方可以放

所以转移就是dp[i][j]=2*dp[i-1][j-2]+dp[i-1][j-1]*(i-2)

int dp[85][10005];

int main(){
    int n,m;
    mem(dp,0);
    dp[1][0]=1;
    for(int i=2;i<=80;i++){
        for(int j=0;j<=10000;j++){
            if(j>0) dp[i][j]=(dp[i][j]+dp[i-1][j-1]*2)%mod;
            if(j>1) dp[i][j]=(dp[i][j]+dp[i-1][j-2]*(i-2))%mod;
        }
    }
    while(scanf("%d%d",&n,&m)&&n){
        printf("%d\n",dp[n][m]);
    }
    return 0;


poj 2479***(基础题,必须好好掌握)

题意:给你n个数的序列,让你其中取两段,最大和是多少

题解:这题其实不难,但是我的写法总不是太好,然后就wa了

这会百度了个不错的方法,先求前i个数的最大区间和,并且要选择i ,f[i]=max(f[i-1]+a[i],a[i]);

然后考虑后i个数最大区间和,并且选择i l[i]=max(l[i+1]+a[i],a[i]);

然后考虑后i个数的最大区间和,不需要一定选择i  rl[i]=max(rl[i+1],l[i]);

然后就考虑两段区间和最大就是 f[i-1]+rl[i]

int a[MAX];
int f[MAX];
int l[MAX];
int rl[MAX];

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        f[0]=0;
        for(int i=1;i<=n;i++){
            f[i]=max(f[i-1]+a[i],a[i]);
        }
        l[n]=a[n];
        for(int i=n-1;i>0;i--){
            l[i]=max(l[i+1]+a[i],a[i]);
        }
        rl[n]=l[n];//从n开始考虑,这个里面考虑的是后i个数的最大区间和,而且必须至少取一个
        for(int i=n-1;i>0;i--){
            rl[i]=max(rl[i+1],l[i]);
        }
        int maxn=-INFF;
        for(int i=2;i<=n;i++){//从2开始考虑,是因为两段中都必须至少取一个,如果两段中加起来只取了一个,那就没法分成两段了
            maxn=max(maxn,f[i-1]+rl[i]);
        }
        printf("%d\n",maxn);
    }
    return 0;
}


我自己的方法就显得特别搓

int a[MAX];
int dp[MAX][3][2];//3是表示0的时候是0段,1的时候是此时已经取了1段,2的时候2段//2表示0的 时候这一个没取,1表示这一个取了

int main(){
    int t;
    scanf("%d",&t);
    while(t--){
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        dp[0][0][0]=0;
        dp[0][0][1]=-INF;
        dp[0][1][0]=-INF;
        dp[0][1][1]=-INF;
        dp[0][2][0]=-INF;
        dp[0][2][1]=-INF;
        for(int i=1;i<=n;i++){
            dp[i][0][0]=0;
            dp[i][1][0]=max(dp[i-1][1][0],dp[i-1][1][1]);
            dp[i][1][1]=max(dp[i-1][0][0],dp[i-1][1][1])+a[i];
            dp[i][2][0]=max(dp[i-1][2][1],dp[i-1][2][0]);
            dp[i][2][1]=max(dp[i-1][1][0],max(dp[i-1][2][1],dp[i-1][1][1]))+a[i];
        }
        printf("%d\n",max(dp[n][2][1],dp[n][2][0]));
    }
    return 0;
}

poj 1050

题意:给你个矩阵,问你其中和最大的子矩阵是多少

题解:这题不是dp,我开头想了好久想不出转移,这题其实就是暴力,不过暴力的要有技巧

我以前一直都是求整个子矩阵的和,然后下一个子矩阵可以由三个子矩阵推出来,然而这个方法很多时候复杂度很高

所以一般存矩阵的和都是只存行的和,或者是列的和

比如存的是列的和,那么就枚举上下两条行,然后遍历一遍列就行了,o(n^3)的复杂度,比直接存子矩阵o(n^4)的复杂度要好

int sum[105][105];

int main(){
    int n;
    scanf("%d",&n);
    mem(sum,0);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            int a;
            scanf("%d",&a);
            sum[i][j]=sum[i-1][j]+a;
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++){
        for(int j=i;j<=n;j++){//枚举行数
            int tmp=0;
            int d=0;
            for(int k=1;k<=n;k++){
                if(tmp<=0) tmp=sum[j][k]-sum[i-1][k];
                else tmp+=sum[j][k]-sum[i-1][k];
                d=max(d,tmp);
            }
            ans=max(ans,d);
        }
    }
    printf("%d\n",ans);
    return 0;
}


poj 1157

题意:给你f种花,还有v种花瓶,然后每种花插每种花瓶都有不同的价值,求最大价值和

题解:我的dp真是弱爆了,连这种题都不能秒

状态转移dp[i][j]=max(dp[i][j-1],dp[i-1][j-1]+a[i][j])

这是考虑前i种花插前j个花瓶,那么第i个插不插第j个,就是转移方法

int a[105][105];
int dp[105][105];

int main(){
    int f,v;
    scanf("%d%d",&f,&v);
    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++){
            scanf("%d",&a[i][j]);
        }
    }
    mem(dp,0);
    for(int i=1;i<=f;i++){
        for(int j=0;j<=v;j++){
            dp[i][j]=-INF;
        }
    }
    for(int i=1;i<=f;i++){
        for(int j=1;j<=v;j++){
            dp[i][j]=max(dp[i-1][j-1]+a[i][j],dp[i][j-1]);
        }
    }
    printf("%d\n",dp[f][v]);
    return 0;
}


我dp虽弱,但是仍然不屈的继续刷题

poj 1276

题意:给你一些钱,有价值,和数量,给你个cash,问你能存到小于等于cash的最大值是多少

题解:多重背包,这题暴力枚举都能过,然而我学了个新的方法,用二进制分解多重背包 转化为01背包

int v[MAX];
int dp[MAXN];

int main(){
    int c,n;
    while(~scanf("%d%d",&c,&n)){
        int xcount=0;
        for(int i=0;i<n;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            for(int k=1;k<=a;k<<=1){
                v[xcount++]=k*b;
                a-=k;
            }
            if(a>0){
                v[xcount++]=a*b;
            }
        }
        mem(dp,0);
        dp[0]=1;
        int flag=0;
        for(int i=0;i<xcount;i++){
            for(int j=c;j>=v[i];j--){
                if(dp[j-v[i]]){
                    dp[j]=1;
                    flag=max(flag,j);
                }
            }
        }
        printf("%d\n",flag);
    }
    return 0;
}


/*****************************树形DP**************************************************************************************************************************************************************/

poj 1192

题意:给你很多定义,题目很长很恶心,单整点集就是图中所有点都连同,只有一条路互相到达,这明显是一棵树,然后求其中连通的一部分的权值最大

题解:用树形dp,从根节点进去,考虑子树取不取,如果子树权值和小于0,那么直接return 0,如果大于就返回这棵子树上的最大权

dp[i]表示,取了这个i节点,这棵树的最大权值和

最后遍历1-n找一下最大值即可,数据貌似很水,我当时瞎做直接输出dp[1]居然过了

int x[MAX];
int y[MAX];
int d[MAX];
struct Edge{
    int v,next;
}edge[MAX*MAX];
int head[MAX];
int dp[MAX];
int tot;

void add_edge(int a,int b){
    edge[tot]=(Edge){b,head[a]};
    head[a]=tot++;
}

void init(){
    mem(head,-1);
    tot=0;
}

int tree_dp(int u,int fa){
    dp[u]=d[u];
    for(int i=head[u];i!=-1;i=edge[i].next){
        int v=edge[i].v;
        if(v==fa) continue;
        dp[u]+=tree_dp(v,u);
    }
    return max(dp[u],0);
}

int main(){
    int n;
    scanf("%d",&n);
    init();
    for(int i=1;i<=n;i++){
        scanf("%d%d%d",&x[i],&y[i],&d[i]);
        for(int j=1;j<i;j++){
            int k=abs(x[i]-x[j])+abs(y[i]-y[j]);
            if(k==1){
                add_edge(i,j);
                add_edge(j,i);
            }
        }
    }
    mem(dp,0);
    tree_dp(1,-1);
    int maxn=0;
    for(int i=1;i<=n;i++) maxn=max(dp[i],maxn);
    printf("%d\n",maxn);
    return 0;
}

/**********************************斜率优化DP*************************************************************************************************/

顾名思义,就是用斜率(数学方法)单调队列来优化dp

可以看这个blog,解释的挺详细http://www.cnblogs.com/ka200812/archive/2012/08/03/2621345.html

当然这只能入门,我也只会做这个样子的题目,其他换个样子估计都不会了

同样的题  HYSBZ 1010

题解:http://paste.ubuntu.net/12228717/

第一次用paste.ubuntu这个东西,感觉不错,文章看着也短了不少

斜率优化dp目前我还只能会这么简单的了,仍需努力,以后再补充


诶补充个题,斜率优化又水了,关键是我连dp都没看出来,为何这么水

poj 3709

题意:给你一串非严格单调递增数列,a0,a1...an-1,每次操作使其中一项-1,然后每项至少要和其他k-1项相等,求最少操作数

题解:如果选定aj,要后面若干项变成aj,假设从ai开始到aj都变成aj,i-k>=j,考虑第i项,寻找满足j+k<=i的某个j,把j-i这些都翻成aj,这就是个dp

转移方程 dp[i]=dp[j]+a[j+1]-a[j+1]+a[j+2]-a[j+1]+......+a[i]-a[j+1]=dp[j]+sum[i]-sum[j]-(i-j)*a[j+1]

这样显然是o(n^2)的复杂度,50W的数据显然过不去,dp[i]=sum[i]+min(dp[j]-sum[j]-(i-j)*a[j+1]),min里面是关于i的线性函数,dp[i]=sum[i]+min(f[i]) (0<=j<=i-k), 计算dp[i]就是看成从f[x]的函数中x=i的情况下寻找最小值,这样的形式就可以用斜率优化dp

假设k<j,j比k的情况更优,那么就是有个数学式子,接一下,得到一边是关于i的,一边是关于j,k的斜率式子

j,k的斜率小于h(i),说明j比k优,接下去就是用单调队列维护解集,单调队列头指针位置的为最优解,每次考虑一个i的时候,头上两个元素是a,b,      如果b,a的斜率小于h(i),那么就是b比a优,头指针+1,直到找到b,a的斜率大于h(i),a就是最优解,然后计算dp[i],然后考虑i进队,结尾两个元素是c,d,如果i,d的斜率小于d,c的斜率,说明i比d更优,如果d,c满足,那么i,d肯定满足,d就不可能变成最优解,所以d出队,知道找到第一个i,d斜率大于d,c的点,然后i进队

然后这题还有个条件,就是单调队列中选择的点必须比i点小k以上,所以在入队的这个地方有个小技巧,i从k开始枚举,因为k以前的i必然都是INF,然后队列中只有0,所以前面的i都是取0的情况,然而这些i还是要入队的,所以只有等i-k>=k的时候在考虑入队,这时候的i肯定比队列里的至少大k  Orz

AC代码  :  http://paste.ubuntu.net/12312005/

斜率dp还需要更深刻的理解,用是会用了


/****************************************数位DP************************************************************************************************/

http://wenku.baidu.com/link?url=XCL1eLAJINNUYeGJBB63niJJLt1qWMrt62eQ0gYgK5avVeQTW8s5s7Ywld0DfheN4NFg8iDFDNDsBx05QzeDcaZptAE1Bmw_wGGMTtg0DdO

数位dp我也只学了最基本的一些玩意,基本属于小白,就先做一下我做了三个入门题的心得把

数位dp是一种搞数字的dp(废话),用位数和那一位的数字作为状态来转移的

比较常用的是dfs写法,然而我并不会,也没做过几个题,最基础的题都是用递推做的


数位dp的方法一般是(最水的题目的方法):

1.预处理dp数组(递推):dp[i][j] 表示在第i位的数字是j的状态下,满足情况的方案数,可以有前导0

处理时枚举位数,然后枚举第i位是啥,然后枚举i-1位是啥

2.求区间 [ l,r ]内满足情况的方案数,同样是从最大位开始枚举考虑,满足情况的就加进去

3.最后solve(r+1)-solve(l),因为solve(n)求的是1-n-1的方案数


首先是hdu 2089

题意:数字中不能出现62和4

题解:dp[i][j]+=dp[i-1][k] ,当j!=4&&!(j==6&&k==2)满足

AC代码:http://paste.ubuntu.net/12228895/


hdu 3555

题意:数字中包含49的个数

题解:我原本正着做,但是就是wa,都不知道是情况,然后只好反着做,求没有49的情况,然后减去,这样的话和上一题一样

AC代码:http://paste.ubuntu.net/12228908/


hdu  3652

题意:数字中出现13并且数字是13的倍数

题解:状态要开四层了dp[i][j][k][h],i,j和前面的一样,k是表示是否已经出现了13,h记录模13以后的余数

状态转移:

if(j==1&&k==3){
      dp[i][j][1][(j*qpow(10,i-1)+h)%13]+=dp[i-1][k][0][h]+dp[i-1][k][1][h];
}
else{
      dp[i][j][1][(j*qpow(10,i-1)+h)%13]+=dp[i-1][k][1][h];
      dp[i][j][0][(j*qpow(10,i-1)+h)%13]+=dp[i-1][k][0][h];
}

求解最后在1-n内的方案数时候比较复杂

int ans=0;
int tmp=0;
int flag=0;
for(int i=tot;i>0;i--){
   for(int j=0;j<digit[i];j++){
        if(flag||(j==3&&digit[i+1]==1)) ans+=dp[i][j][1][(13-tmp)%13]+dp[i][j][0][(13-tmp)%13];
        else ans+=dp[i][j][1][(13-tmp)%13];
    }
    if(digit[i]==3&&digit[i+1]==1)  flag=1;
    tmp=(tmp+digit[i]*qpow(10,i-1)%13)%13;
}


tmp是记录i位时,前面几位留下来的余数,因为前面没有除尽的后面要接着模,因为如果是555,就是先把0,1,2,3,4开头的情况全部加进去,5的时候考虑下一位,如果求的数字中有13这两位,那他们后面可以直接考虑存在13或者不存在13,如果没有出现之前必须考虑存在13的情况,然后余数就是后i位的余数+前面留下来的余数要被13整除

这题说通了也不难,但是自己写的时候卡了好久,唉继续努力,明天又是周一了,燃烧ing


AC代码:http://paste.ubuntu.net/12228933/





版权声明:本文为Miracle_ma原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。