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

题目

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

这个国家由 声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】