DP练习题二

缺乏、安全感 2023-10-11 10:13 10阅读 0赞

# DP练习题二 #

虽然欠一大堆题，但是想着无论如何DP一定要多做题，不然根本就是扯淡。。。。。。  
可能看上去状态转移方程比较简单，但是真的想出来也太难了吧，感觉现在每道题自己都想不到怎么做，多刷题找感觉了

一、[POJ 1239：Increasing Sequences][POJ 1239_Increasing Sequences]

这道题题意还是比较容易懂吧，给定一个字符串都是由数字构成，求将一些数字合并获得的子序列成递增子序列，要求最后一个数尽量小，如果有多个数据满足，则保证第一个数字尽量大，如果还有多个，则是第二个数尽量大，以此类推。。。

看到题然后一脸懵逼，也太难了吧，看了十几分钟完全没思路，于是就看了大佬的题解，**两次DP**解决问题，说起来相当容易，但是现在这水平也只能看看大佬们的代码自己找找感觉了

接下来参考的下面的博客：  
[https://blog.csdn.net/cc\_again/article/details/12208725\#][https_blog.csdn.net_cc_again_article_details_12208725]

**第一次从前往后dp,dp\[i\]表示包括第i位往前，满足题目要求能得到的最小长度。这样就可以求出，最后一个最小的满足的数了。  
求出最后一个最小的数后，从后往前dp,dp\[i\]表示从第i位开始往后，在满足题目要求的情况下，能得到的最大长度。这样就可以求出，按顺序依次最大的了。**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    char str[100];
    int dp[100];
    bool isGreater(int i,int j,int m,int n){
               //判断从i到j的串是否大于从m到n的串
        while(str[i]=='0'&&i<=j)         //去掉前导0
            i++;
        while(str[m]=='0'&&m<=n)        //去掉前导0
            m++;
        if(i>j)
            return false;
        if(m>n)
            return true;
        int a=j-i+1;
        int b=n-m+1;          //位数
        if(a>b)
            return true;
        else if(a<b)
            return false;
        else{
                                //位数相同，逐位比较
            for(int k=i,p=m;k<=j;k++,p++){
        
                if(str[k]>str[p])
                    return true;
                else if(str[k]<str[p])
                    return false;
            }
        }
        return false;            //等于的情况
    }
    int main()
    {
        
        while(~scanf("%s",str+1)){
        
            int n=strlen(str+1);
            if(str[1]=='0'&&n==1)
                break;
            dp[1]=1;           i
            //dp[i]表示从第i位往前长度最小为dp[i]组成一个数字的情况
            for(int i=2;i<=n;i++){
        
                dp[i]=i;
                for(int j=i-1;j>=1;j--){
        
                    if(isGreater(j+1,i,j-dp[j]+1,j)){
        
                        dp[i]=i-j;            //求出满足题意的最小长度
                        break;
                    }
                }
            }
    
            //然后从后往前，dp[i]表示在满足第一个条件的情况下，从i开始的最大长度
            int tt=n-dp[n]+1;
            dp[tt]=dp[n];
            for(int i=tt-1;i>=1;i--){
        
                if(str[i]=='0'){
        
                    dp[i]=dp[i+1]+1;
                    continue;
                }
                for(int j=tt;j>i;j--){
                    //求出长度最大的
                    if(isGreater(j,j+dp[j]-1,i,j-1)){
        
                        dp[i]=j-i;
                        break;
                    }
                }
            }
            for(int i=1;i<=dp[1];i++){
        
                printf("%c",str[i]);
            }
            int pp=dp[1]+1;
            while(pp<=n){
        
                printf(",");
                for(int i=pp;i<pp+dp[pp];i++)
                    printf("%c",str[i]);
                pp=pp+dp[pp];
            }
            printf("\n");
        }
        //getchar();
        return 0;
    }

[二、POJ 1976：A Mini Locomotive][POJ 1976_A Mini Locomotive]

一道类似于0-1背包的思路，还算比较简单吧

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int  a[50010];
    int dp[5][50010];            //类似于0-1背包
    int sum[50010];
    //运用前缀和思想
    int main()
    {
        
        int t,n;
        int k;
        scanf("%d",&t);
        while(t--){
        
            memset(dp,0,sizeof(dp));
            memset(a,0,sizeof(a));
            memset(sum,0,sizeof(sum));
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
        
                scanf("%d",&a[i]);
                sum[i]=sum[i-1]+a[i];
            }
            scanf("%d",&k);
            for(int i=1;i<=3;i++){
        
                for(int j=k;j<=n;j++){
        
                    dp[i][j]=max(dp[i][j-1],dp[i-1][j-k]+sum[j]-sum[j-k]);
                }
            }
            printf("%d\n",dp[3][n]);
        }
        return 0;
    }

[三、POJ 1018：Communication System][POJ 1018_Communication System]

可以说并不是一道真正意义上的dp题，用贪心等方法都可以解决 ，但是为了很好的熟悉dp，还是用的dp解法。

下面参考的下面博客：  
[https://blog.csdn.net/huayunhualuo/article/details/47780877][https_blog.csdn.net_huayunhualuo_article_details_47780877]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define inf 0x3f3f3f3f
    using namespace std;
    int dp[200][2000];       //买i件设备时，最小值为k时的花费
    int main()
    {
        
        int t;
        int n,m;
        int b,p;
        scanf("%d",&t);
        while(t--){
        
            scanf("%d",&n);
            memset(dp,inf,sizeof(dp));
            for(int i=0;i<2000;i++)       //当没有一件设备时，自然p为零
                dp[0][i]=0;
            for(int i=1;i<=n;i++){
        
                scanf("%d",&m);
                for(int j=1;j<=m;j++){
        
                    scanf("%d%d",&b,&p);
                    for(int k=0;k<2000;k++){
        
                        if(b<=k)         
                        //当买的b值比k值小时，说明在你买的设备中最小的为b，所以在买i-1件设备中花费+p与dp[i][b]取小值
                            dp[i][b]=min(dp[i-1][k]+p,dp[i][b]);
                        else
                            dp[i][k]=min(dp[i][k],dp[i-1][k]+p);
                            //买的b值比k值大时，k时买的设备中的最小值，同上
                    }
                }
            }
            double ans=0;
            //遍历找出b/p的最大值
            for(int i=1;i<2000;i++){
        
                if(dp[n][i]!=inf){
        
                    if(ans<(i*1.0/dp[n][i]))
                        ans=(i*1.0/dp[n][i]);
                }
            }
            //getchar();
            printf("%.3f\n",ans);
            //getchar();
        }
        return 0;
    }

[四、POJ 1837：Balance][POJ 1837_Balance]

参考的这位大佬的博客：[https://blog.csdn.net/lyy289065406/article/details/6648094/][https_blog.csdn.net_lyy289065406_article_details_6648094]

开始乍一眼看感觉还是很简单的，感觉暴力就行啊，但是仔细一想这怎么可以啊，这时间复杂度完全爆炸了啊。。。。。。

因为这个专题训练是DP，于是就想着看看怎么找状态转移方程，但是实在想不到怎么构造状态转移方程，具体思路见那位大佬博客，

首先想着平衡度问题，于是可以构造dp\[i\]\[j\]表示**挂满i个砝码，平衡度为j**

w\[\]数组表示砝码编号；  
c\[\]数组表示砝码重量；

由于距离c\[i\]的范围是-1515，钩码重量的范围是125，钩码数量最大是20

因此最极端的平衡度是所有物体都挂在最远端，因此平衡度最大值为j=15\*20 \*25=7500。原则上就应该有dp\[ 1~20 \]\[-7500 ~ 7500 \]。

于是构造状态方程有：**状态方程dp\[i\]\[ j+ w\[i\] \* c\[k\] \]= ∑（dp\[i-1\]\[j\]）**

还是感觉稍微有点难，这个DP估计还是很难突破，

#include<cstdio>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int dp[30][15010];
    int c[30];
    int w[30];
    int main(){
        
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
        
            scanf("%d",&c[i]);
        }
        for(int i=1;i<=m;i++){
        
            scanf("%d",&w[i]);
        }
        memset(dp,0,sizeof(dp));
        dp[0][7500]=1;
    
        for(int i=1;i<=m;i++){
        
            for(int j=0;j<=15000;j++){
        
                if(dp[i-1][j]){
        
                    for(int k=1;k<=n;k++){
        
                        dp[i][j+w[i]*c[k]]+=dp[i-1][j];
                    }
                }
            }
        }
        //getchar();
        printf("%d\n",dp[m][7500]);
        //getchar();
        return 0;
    }

[五、POJ 1276：Cash Machine][POJ 1276_Cash Machine]

看题目感觉不难，就是一个背包的变形嘛，但是多重背包现在还没遇到几道题，然后就有点迷，一直没有想到怎么搞（当然，这里贪心是绝对不行的）

[https://blog.csdn.net/lyy289065406/article/details/6648102][https_blog.csdn.net_lyy289065406_article_details_6648102]  
又是这位大佬的链接，感觉讲的挺好的，其实其核心还是0-1背包，就是要考虑其他东西，导致这题我开始没想出来，

由于POJ 测试数据水，于是我没有new动态数组，直接用的静态数组；

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int num[100000];
    int w[100000];
    int c[100000];
    int dp[100000];
    int cnt[100000];
    int main(){
        
        int  n,moneynum;
        while(~scanf("%d%d",&moneynum,&n)){
        
            memset(num,0,sizeof(num));
            memset(c,0,sizeof(c));
            memset(w,0,sizeof(w));
            memset(dp,0,sizeof(dp));
            for(int i=1;i<=n;i++){
        
                scanf("%d%d",&num[i],&w[i]);
                c[i]=w[i];
            }
            /*for(int i=1;i<=n;i++){
                printf("num[%d]=%d,w[%d]=%d\n",i,num[i],i,w[i]);
            }*/
            memset(cnt,0,sizeof(cnt));
            for(int i=1;i<=n;i++){
        
                memset(cnt,0,sizeof(cnt));
                for(int j=w[i];j<=moneynum;j++){
        
                    if(dp[j]<dp[j-c[i]]+w[i]&&cnt[j-c[i]]<num[i]){
        
                        dp[j]=dp[j-c[i]]+w[i];
                        cnt[j]=cnt[j-c[i]]+1;
                    }
                }
            }
            //getchar();
            printf("%d\n",dp[moneynum]);
            //getchar();
        }
        return 0;
    }

[POJ 1239_Increasing Sequences]: http://poj.org/problem?id=1239
[https_blog.csdn.net_cc_again_article_details_12208725]: https://blog.csdn.net/cc_again/article/details/12208725#
[POJ 1976_A Mini Locomotive]: http://poj.org/problem?id=1976
[POJ 1018_Communication System]: http://poj.org/problem?id=1018
[https_blog.csdn.net_huayunhualuo_article_details_47780877]: https://blog.csdn.net/huayunhualuo/article/details/47780877
[POJ 1837_Balance]: http://poj.org/problem?id=1837
[https_blog.csdn.net_lyy289065406_article_details_6648094]: https://blog.csdn.net/lyy289065406/article/details/6648094/
[POJ 1276_Cash Machine]: http://poj.org/problem?id=1276
[https_blog.csdn.net_lyy289065406_article_details_6648102]: https://blog.csdn.net/lyy289065406/article/details/6648102