阅读量:0
洛谷：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]; }