DP练习

2024-03-17 02:18| 来源: 网络整理| 查看: 265

DP练习-初阶题（洛谷）前言：

DP对我来说，一直都是比较令我头大的，现在的水平都是处于入门级的水平，这一周基本上主要就是强化DP

虽然关于DP的博客写过一点题解，但是那时候都是处于半懵的状态，但是我觉得有篇DP入门的博客还是很好的，还是打算给贴出来

链接：

DP入门题总结

个人觉得这篇博客还是可以的，就是几道经典的DP题目

第二个链接是：100个动规方程

100个动规方程

这是转载的大佬的，DP的题数不胜数，肯定是做不完的，主要是想通过做题找到寻找状态转移方程的策略和灵感

废话不多说，先复习复习这两天做的题目吧。。。。

题目汇总第一类：背包初阶版：

说到背包，背包9讲是肯定要提的这里给出链接：

背包九讲

背包九讲，觉得真的讲的很详细了，虽然后面几讲看的还是有点小迷。。。但是基本上背包问题，都可以直接或间接的转化为0-1背包问题

还是要做题：

一、洛谷 P1060：开心的金明

题意： n块钱，m个物品，每个物品都有对应的价格w[i]和还有重要度v[i]。要求最终能够得到价格和重要度的乘积之和最大

题解：看上去很像0-1背包，但是又感觉和0-1背包有那么一丢丢的区别，0-1背包问题是求最终获得的价值总和最大，于是仔细一想，为什么不把价格和重要度相乘v[i]=v[i]*w[i]，这样就和0-1背包问题等价了啊这道题就迎刃而解了

题意： M元钱，n种菜（每个菜的数量只有一份），每种菜都有对应的价格w[i]，求：刚好把钱花完的条件下，最多有多少种点菜方式

题解：其实如果要说，也是一道0-1背包的变形题，动规方程怎么找呢，开始真的很迷，看了题解才有种恍然大悟的感觉状态转移方程：定义dp[i][j]为用前i道菜用光j元钱的办法总数，其状态转移方程如下：（1）if(j==第i道菜的价格)dp[i][j]=dp[i-1][j]+1;

（2）if(j>第i道菜的价格) dp[i][j]=dp[i-1][j]+dp[i-1][j-第i道菜的价格];

（3）if(j scanf("%d",&w[i]); } memset(dp,0,sizeof(dp)); for(int i=1;i if(j>w[i]){ dp[i][j]=dp[i-1][j]+dp[i-1][j-w[i]]; } else if(j==w[i]) dp[i][j]=dp[i-1][j]+1; else dp[i][j]=dp[i-1][j]; } } printf("%d\n",dp[n][m]); return 0; } 三、洛谷P1048：采药

题意： m株草药，n单位的时间，每株草药都有对应的价值v[i]和所需要耗费的时间w[i]

题解：就是个裸的0-1背包，不过多解释，直接贴代码：

题意：箱子的容量为m，有n个物品，每个物品有一个体积w[i]尽量多的装入箱子中，使得箱子剩余容量最少

题解：其实也就是0-1背包的简单变形，题目求最终箱子剩余容量最少，于是换个角度不就是求装的容量最大，然后用箱子的容量减去该值即为所求。不妨设：v[i]=w[i]，这样就转化为了最熟悉的0-1背包问题，于是乎就解决了

题意：就是上面的第三题P1048的变形，0-1背包问题变成了完全背包问题。

题解：也不多解释，就是一个完全背包的模板题

#include #include #include #include #include #include #include #include #include #include #define INF 0x3f3f3f3f #define ll long long #define pi acos(-1.0) using namespace std; const int maxn=1e7; int v[maxn+10]; int w[maxn+10]; int dp[maxn+10]; int n,m; int main(){ scanf("%d%d",&m,&n); for(int i=1;i for(int j=w[i];j int v,p,q; }a[maxn]; int n,m; int main(){ scanf("%d%d",&n,&m); for(int i=1;i if(!a[i].q){ for(int j=1;j h[j]=f[j-a[i].v]+a[i].p; } for(int j=1;j for(int k=n;k>=a[i].v+a[j].v;k--){ h[k]=max(h[k],h[k-a[j].v]+a[j].p); } } } for(int j=a[i].v;j n=1; int t=1; while(cin>>a[n++]){ //if(t==8) // break; //t++; } n--; d1[1]=a[1],d2[1]=a[1]; int len1=1,len2=1; for(int i=2;i d1[++len1]=a[i]; } else{ int p1=upper_bound(d1+1,d1+1+len1,a[i],greater())-d1; d1[p1]=a[i]; } if(d2[len2] int p2=lower_bound(d2+1,d2+1+len2,a[i])-d2; d2[p2]=a[i]; } } cout scanf("%d",&a[i]); } int t=1; for(int i=n; i>=1; i--) { b[t++]=a[i]; } for(int i=1;i if(a[i]>a[j]){ dp1[i]=max(dp1[i],dp1[j]+1); } } } for(int i=n;i>=1;i--){ for(int j=n+1;j>i;j--){ if(a[i]>a[j]){ dp2[i]=max(dp2[i],dp2[j]+1); } } } int maxnum=0; for(int i=1;i ll startTime,endTime; }; node z[maxn+10]; bool cmp(node a,node b){ return a.startTime>b.startTime; } int main(){ ll n,k,num=1; scanf("%lld%lld",&n,&k); for(ll i=1;i if(sum[i]==0){ f[i]=f[i+1]+1; } else{ for(ll j=1;j f[i]=f[i+z[num].endTime]; num++; } } } } cout scanf("%d",&a[i]); a[i+n]=a[i]; sum[i]=sum[i-1]+a[i]; dp1[i][i]=0; } for(int i=n+1;i for(int i=1;i dp1[i][j]=min(dp1[i][j],dp1[i][k]+dp1[k+1][j]+sum[j]-sum[i-1]); dp2[i][j]=max(dp2[i][j],dp2[i][k]+dp2[k+1][j]+sum[j]-sum[i-1]); } } } int ans1=0x3f3f3f3f; int ans2=0; for(int i=1;i for(int j=1;j {5,-1,-2,-1,-3}, {-1,5,-3,-2,-4}, {-2,-3,5,-2,-2}, {-1,-2,-2,5,-1}, {-3,-4,-2,-1,0} }; int la,lb; int a[maxn],b[maxn]; int dp[maxn][maxn]; string sa,sb; int main(){ cin>>la>>sa; cin>>lb>>sb; for(int i=1;i dp[i][j]=-INF; } } for(int i=1;i if(sb[i-1]=='A') b[i]=0; if(sb[i-1]=='C') b[i]=1; if(sb[i-1]=='G') b[i]=2; if(sb[i-1]=='T') b[i]=3; } for(int i=1;i dp[i][j]=max(dp[i][j],dp[i][j-1]+table[b[j]][4]); dp[i][j]=max(dp[i][j],dp[i-1][j]+table[a[i]][4]); dp[i][j]=max(dp[i][j],dp[i-1][j-1]+table[a[i]][b[j]]); } } printf("%d\n",dp[la][lb]); return 0; } 第三类：多维动态规划一、洛谷P1508：Likecloud-吃、吃、吃

题意：有一个人从最下面中间开始走，走到最上面，但是要求是走的话只能向前走（也就是正前方，左前方，右前方；不能回头），每个点都有一个对应点价值，求：最终获得的价值和最大

题解：其实这还是很容易想到dp的，状态转移方程为： dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+mp[i][j];

于是代码为：

#include #include #include #include #include #include #include #include #include #include #include #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=1000; int mp[maxn][maxn]; int dp[maxn][maxn]; int n,m; int main(){ memset(dp,0,sizeof(dp)); memset(mp,-inf,sizeof(mp)); cin>>m>>n; int sx,sy; sx=m,sy=n/2+1; for(int i=1;i scanf("%d",&mp[i][j]); } } for(int i=1;i dp[i][j]=max(max(dp[i-1][j],dp[i-1][j-1]),dp[i-1][j+1])+mp[i][j]; } } printf("%d\n",max(max(dp[sx][sy],dp[sx][sy-1]),dp[sx][sy+1])); return 0; } 二、洛谷P1006：传纸条

题意： n行m列矩阵，每个点都有对应的价值。从左上角走到有下角，然后再从右下角走到左上角，要求不能重复走，然后求：获得的最大价值和

题解：其实也是很容易想到DP的，但是比较复杂的是：它不能要求重复，开始还是比较容易想到思维dp的，但是后面看题解说，如果数据量稍微大一点思维，就有可能为tle 状态转移方程为： dp[i][j][k][l]=max(dp[i][j-1][k-1][l],dp[i-1][j][k][l-1],dp[i][j-1][k][l-1],dp[i-1][j][k-1][l])+mp[i][j]+mp[k][l]; （其中i，j表示去，k，l表示回，要求不能重复，所有l>j）

于是完整代码为：

#include #include #include #include #include #include #include #include #include #include #include #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=55; int mp[maxn][maxn]; int dp[maxn][maxn][maxn][maxn]; int n,m; int max_num(int a,int b,int c,int d){ if(a for(int j=1;j for(int j=1;j for(int l=j+1;l dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; }

完整代码：

#include #include #include #include #include #include #include #include #include #include #include #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=110; int n,m; int mp[maxn][maxn]; int dp[maxn][maxn]; int main(){ cin>>n>>m; for(int i=1;i scanf("%d",&mp[i][j]); } } for(int i=1;i if(mp[i][j]==1){ dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1; } } } int ans=0; for(int i=1;i ans=max(ans,dp[i][j]); } } cout return x.c*y.b scanf("%lld",&w[i].a); } for(ll i=1;i scanf("%lld",&w[i].c); } //先进行排序，然后就是0-1背包处理 sort(w+1,w+n+1,cmp); for(ll i=1;i dp[j]=max(dp[j],dp[j-w[i].c]+w[i].a-j*w[i].b); } } ll ans=0; for(ll i=1;i cin>>n>>m>>t; for(int i=1;i for(int j=m;j>=w1[i];j--){ for(int k=t;k>=w2[i];k--){ dp[j][k]=max(dp[j][k],dp[j-w1[i]][k-w2[i]]+1); } } } printf("%d\n",dp[m][t]); return 0; } 六、洛谷P1736：创意吃鱼法

题意：给一个只含0 、1矩阵，然后求：一个子矩阵为正方形，而且只有对角线为1，其余都为0。求对角的最大长度

题解：不懂。。。。只能附一个别人的题解了在这里插入图片描述

#include #include #include #include #include #include #include #include #include #include #include #define ll long long #define inf 0x3f3f3f3f using namespace std; const int maxn=2510; int n,m; int mp[maxn][maxn]; int s1[maxn][maxn]; int s2[maxn][maxn]; int dp[maxn][maxn]; int main(){ cin>>n>>m; int ans=0; //第一遍：左上->右下 for(int i=1;i scanf("%d",&mp[i][j]); if(mp[i][j]==0){ s1[i][j]=s1[i][j-1]+1; s2[i][j]=s2[i-1][j]+1; } else{ dp[i][j]=min(dp[i-1][j-1],min(s1[i][j-1],s2[i-1][j]))+1; } ans=max(ans,dp[i][j]); } } //第二遍：右上->左下 memset(dp,0,sizeof(dp)); memset(s1,0,sizeof(s1)); memset(s2,0,sizeof(s2)); for(int i=1;i if(mp[i][j]==0){ s1[i][j]=s1[i][j+1]+1; s2[i][j]=s2[i-1][j]+1; } else{ dp[i][j]=min(dp[i-1][j+1],min(s1[i][j+1],s2[i-1][j]))+1; } ans=max(ans,dp[i][j]); } } cout

【本文地址】

公司简介

联系我们