您的位置:首页 > 游戏 > 手游 > dp专题(二)

dp专题(二)

2024/11/16 21:46:46 来源:https://blog.csdn.net/2301_80718054/article/details/140869429  浏览:    关键词:dp专题(二)

洛谷:B3626 跳跃机器人

题目描述

地上有一排格子,共 nn 个位置。机器猫站在第一个格子上,需要取第 nn 个格子里的东西。

机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:

  • 初始时,机器人位于 11 号格子
  • 若机器人目前在 xx 格子,那么它可以跳跃到 x−1,x+1,2xx−1,x+1,2x 里的一个格子(不允许跳出界)

问机器人最少需要多少次跳跃,才能到达 nn 号格子。

输入格式

仅一行,一个正整数,表示 nn。

输出格式

仅一行,一个正整数,表示最少跳跃次数。

输入 #1复制

30

输出 #1复制

6

输入 #2复制

50

输出 #2复制

7

输入 #3复制

64

输出 #3复制

6

输入 #4复制

63

输出 #4复制

8
样例解释

第一组样例:
1→2→4→8→16→15→301→2→4→8→16→15→30

第二组样例:
1→2→3→6→12→24→25→501→2→3→6→12→24→25→50

第三组样例:
1→2→4→8→16→32→641→2→4→8→16→32→64

第四组样例:
1→2→4→8→16→32→31→62→631→2→4→8→16→32→31→62→63

请注意在本组样例中,6363 不能通过 64−164−1 得到,因为格子总数为 6363,没有第 6464 个格子。

数据规模与约定

对于 100%100% 的数据,有 1≤n≤10000001≤n≤1000000。

做法

dp数组 下标:第i格 ; 值:步数

感觉有点递推关系的都可以考虑一下dp

#include<bits/stdc++.h>
using namespace std;
int n;
int dp[1000010];
int main(){scanf("%d",&n);memset(dp,0x3f,sizeof(dp));dp[1]=0;for(int i=2;i<=n;i++){dp[i]=dp[i-1]+1;if(i%2==0){dp[i]=min(dp[i],dp[i/2]+1);dp[i-1]=min(dp[i-1],dp[i]+1);}}cout<<dp[n];
}

2024黑龙江省赛:J. Trade

题目

在一个繁荣的国家,金斯诺决定从事贸易。

这个国家由 𝑛∗𝑚n∗m 座城市组成。每个城市由一对整数 (𝑥,𝑦)(x,y) 表示,其中 1≤𝑥≤𝑛1≤x≤n 和 1≤𝑦≤𝑚1≤y≤m 表示其在网格中的位置。在城市 (𝑥,𝑦)(x,y) 中,物品的价格用 𝑎[𝑥][𝑦]a[x][y] 表示,到达该城市的旅行费用用 𝑏[𝑥][𝑦]b[x][y] 表示。

在踏上旅程之前,金斯诺需要你为他规划一条路线。路线必须符合以下条件:

  • 路线的起点必须是位于第一行第一列的城市,即 (1,1)(1,1) 。
  • 路线的终点必须是位于最后一行( 𝑥=𝑛x=n )或最后一列( 𝑦=𝑚y=m )的城市。
  • 金斯诺只能从城市 (𝑥𝑖,𝑦𝑖)(xi,yi) 移动到 (𝑥𝑖+1,𝑦𝑖)(xi+1,yi) 或 (𝑥𝑖,𝑦𝑖+1)(xi,yi+1) 。因此,对于路线中的每一步 𝑖i (路线中的最后一步除外), (𝑥𝑖+1,𝑦𝑖+1)(xi+1,yi+1) 必须选择在 (𝑥𝑖,𝑦𝑖)(xi,yi) 的正下方或正右方。

进入路线后,Kingsnow 将在路线的第一个城市 (1,1)(1,1) 购买一件物品。然后,他将任意选择路线上的另一个城市出售该物品。此外,从他开始旅行的城市到他出售物品的城市之间,每到一个城市,他都会支付旅行费用。

也就是说,对于任何给定的路线 (𝑥1,𝑦1),(𝑥2,𝑦2),...,(𝑥𝑘,𝑦𝑘)(x1,y1),(x2,y2),...,(xk,yk) ,Kingsnow 都会从区间 [2,𝑘][2,k] 中任意选择一个整数 𝑡t 。他在城市 (𝑥𝑡,𝑦𝑡)(xt,yt) 出售商品的利润计算公式为 Profit=𝑎[𝑥𝑡][𝑦𝑡]−𝑎[1][1]−∑𝑡𝑖=1𝑏[𝑥𝑖][𝑦𝑖]Profit=a[xt][yt]−a[1][1]−∑i=1tb[xi][yi]

金斯诺寻找的路线是,无论他选择在路线上的哪个城市出售物品,他都能获得非负利润。

输入

第一行包含两个整数 𝑛n 和 𝑚(1≤𝑛,𝑚≤1000)m(1≤n,m≤1000) - 行数和列数。确保 𝑛n 和 𝑚m 不同时等于 11 。

在接下来的 𝑛n 行中,每一行都包含范围为 [1,109][1,109] 的 𝑚m 个整数,表示物品在每个城市的价格。第 𝑥x 行中的第 𝑦y 个整数是 𝑎[𝑥][𝑦]a[x][y] 。

在接下来的 𝑛n 行中,每一行都包含 𝑚m 个整数,范围为 [1,109][1,109] ,表示每个城市的差旅费用。第 𝑥x 行中的第 𝑦y 个整数是 𝑏[𝑥][𝑦]b[x][y] 。

输出

如果至少有一条路由符合要求,则输出 "是",否则输出 "否"。

做法

dp数组 下标:位于i行j列  ; 值:旅行费用

#include<bits/stdc++.h>
using namespace std;int n,m;
long long a[1010][1010],b[1010][1010],dp[1010][1010];int main(){scanf("%d%d",&n,&m);memset(dp,0x3f3f3f3f3f3f3f3f,sizeof(dp));for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%lld",&a[i][j]);}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){scanf("%lld",&b[i][j]);}}dp[1][0]=dp[0][1]=0;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]-a[1][1]-dp[i-1][j]>=0) dp[i][j]=min(dp[i-1][j]+b[i][j],dp[i][j]);if(a[i][j]-a[1][1]-dp[i][j-1]>=0) dp[i][j]=min(dp[i][j-1]+b[i][j],dp[i][j]);}}if(dp[n][m-1]!=0x3f3f3f3f3f3f3f3f||dp[n-1][m]!=0x3f3f3f3f3f3f3f3f) cout<<"YES";else cout<<"NO";
}

牛客小白月赛95:E.相依

题目描述

此题为C题的hard版,只有aia_iai​的数据范围不同。

给你一个 nnn 个正整数组成的数组 a ,你每次操作可以选择一对 (i,j)( i, j )(i,j),满足 1≤i<j≤n1 \leq i < j \leq n1≤i<j≤n,且 ai=aja_{i} = a_{j}ai​=aj​ ,将 { ai,ai+1,...,aj−1,aja_{i} , a_{i+1} , ... , a_{j-1} , a_{j}ai​,ai+1​,...,aj−1​,aj​ } 这段数删除,操作之后数组变为 { a1,a2,...,ai−1,aj+1,...,an−1,ana_{1},a_{2}, ..., a_{i-1},a_{j+1}, ...,a_{n-1},a_{n}a1​,a2​,...,ai−1​,aj+1​,...,an−1​,an​ }。文文想知道最少要做多少次操作才能将数组变为空。

输入描述:

第一行一个正整数输入 nnn (1≤n≤5×105)( 1 \leq n \leq 5 \times 10^5 )(1≤n≤5×105)。

第二行依次输入 nnn 个正整数 a1,a2,...,an−1,ana_{1},a_{2},...,a_{n-1},a_{n}a1​,a2​,...,an−1​,an​,每个数之间以空格分开。(0≤ai≤n)( 0 \leq a_i \leq n )(0≤ai​≤n)

输出描述:

输出一行,代表最少的操作次数,如果无论如何都无法使数组为空就输出 -1。

示例1

输入

5
3 2 3 2 2

输出

2

说明

例如,n 为 5,数组为{3,2,3,2,2}\{3, 2, 3, 2, 2\}{3,2,3,2,2},第一次操作我们可以选择 i=1i = 1i=1,j=3j = 3j=3,把这一段删除后数组变为 {2,2}\{2, 2\}{2,2},第二次操作我们可以选择 i=1i = 1i=1,j=2j = 2j=2,把这一段删除后数组变为空,操作了两次。

示例2

输入

5
1 2 3 4 5

输出

-1

做法

dp数组  下标:消除前i个   ;  值:最小操作次数

这题一开始我在怀疑dp的正确性,然后举了几个样例发现他确实能完美解决,还挺神奇的。只能说以后尽量往这个方向靠了,太难想了。

不过最值是一个标志。

//O(n^2)做法
#include<bits/stdc++.h>
using namespace std;
int n;
int a[500010],dp[500010];
int main(){memset(dp,0x3f,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}dp[0]=0;for(int i=1;i<=n;i++){for(int j=1;j<i;j++){if(a[i]==a[j]){//找前面和当前数字相同的且操作数最小的dp[i]=min(dp[i],1+dp[j-1]);}}}if(dp[n]==0x3f3f3f3f) cout<<-1;else cout<<dp[n]; 
}//O(n)做法
#include<bits/stdc++.h>
using namespace std;int n;
int a[500010],dp[500010],minn[500010];int main(){memset(dp,0x3f,sizeof(dp));memset(minn,0x3f,sizeof(dp));scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a[i]);}dp[0]=0;for(int i=1;i<=n;i++){dp[i]=minn[a[i]];//前面和当前数字相同的且操作数最小的可以用数组minn来维护,实现降低复杂度minn[a[i]]=min(minn[a[i]],dp[i-1]+1);}if(dp[n]!=0x3f3f3f3f) cout<<dp[n];else cout<<-1; }

2024河南省赛:L-Toxel 与 PCPC II

做法

dp数组  考虑了第i个bug ,解决了j个bug  ; 值:需要的时间 

有时候用滚动数组也会超时,直接降维就好了。

这题的关键在于:如果连续修复太多个bug的话这个数得四次方是远大于从头开始扫描的时间,22的四次方刚好是大于2e5最小整数,所以就可以利用这点降低复杂度。

//最开始的思路
#include<bits/stdc++.h>
using namespace std;int n,m;
long long a[200010],dp[2010][2010];int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%lld",&a[i]);for(int i=0;i<=m;i++){for(int j=0;j<=m;j++){dp[i][j]=0x3f3f3f3f3f3f3f3f;}}sort(a+1,a+1+m);dp[0][0]=0;for(int i=1;i<=m;i++){int j=0;if(i-j>22) j=i-21;for(;j<=i;j++){if(j==0) dp[i][j]=0;//一个都不解决 else if(i!=j) dp[i][j]=min(dp[i][j],dp[j][j]);//只解决了前j个不解决 if(i==j){//全部都解决了int k=0;if(j-k>22) k=j-22;for(;k<j;k++){//i个问题解决了k个 if(k==0) dp[i][j]=min(dp[i][j],a[i]+1ll*i*i*i*i);//一次性解决 else dp[i][j]=min(dp[i][j],a[i]+1ll*(i-k)*(i-k)*(i-k)*(i-k)+dp[k][k]);//已经解决了前k个 }}}}cout<<dp[m][m];}//可以看到,数组开不下,用滚动数组也会超时。但我们可以发现,这题直接降维就好了,因为大的值由小的覆盖,不用担心上层和这层乱赋值的情况。
#include<bits/stdc++.h>
using namespace std;
int n,m;
long long a[200010],dp[200010];
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++) scanf("%lld",&a[i]);for(int j=0;j<=m;j++){dp[j]=0x3f3f3f3f3f3f3f3f;}sort(a+1,a+1+m);dp[0]=0;for(int i=1;i<=m;i++){int j=0;if(i-j>22) j=i-21;for(;j<=i;j++){if(j==0) dp[j]=0;//不解决 else if(i!=j) dp[j]=min(dp[j],dp[j]);if(i==j){int k=0;if(j-k>22) k=j-21;for(;k<j;k++){if(k==0) dp[j]=min(dp[j],a[i]+1ll*i*i*i*i);else dp[j]=min(dp[j],a[i]+1ll*(i-k)*(i-k)*(i-k)*(i-k)+dp[k]);}}}}cout<<dp[m];}

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com