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 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< 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 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 第一行一个正整数输入 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 示例2 dp数组 下标：消除前i个 ； 值：最小操作次数 这题一开始我在怀疑dp的正确性，然后举了几个样例发现他确实能完美解决，还挺神奇的。只能说以后尽量往这个方向靠了，太难想了。 不过最值是一个标志。 dp数组 考虑了第i个bug ,解决了j个bug ； 值：需要的时间 有时候用滚动数组也会超时，直接降维就好了。 这题的关键在于：如果连续修复太多个bug的话这个数得四次方是远大于从头开始扫描的时间，22的四次方刚好是大于2e5最小整数，所以就可以利用这点降低复杂度。输入描述:
输出描述:
输出一行，代表最少的操作次数，如果无论如何都无法使数组为空就输出 -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，把这一段删除后数组变为空，操作了两次。 输入
5 1 2 3 4 5
输出
-1
做法
//O(n^2)做法 #include2024河南省赛：L-Toxel 与 PCPC II
做法
//最开始的思路 #include