B3626 跳跃机器人——洛谷（疑问）

本文主要是介绍B3626 跳跃机器人——洛谷（疑问），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

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

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

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

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

输入格式

仅一行，一个正整数，表示 �n。

输出格式

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

输入输出样例

输入 #1复制

输出 #1复制

输入 #2复制

输出 #2复制

输入 #3复制

输出 #3复制

输入 #4复制

输出 #4复制

说明/提示

样例解释

第一组样例：
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≤�≤10000001≤n≤1000000。

想法：

老想法，想用dfs写，超时了，还re了，应该可以写的吧dfs，本来只是想记录一下不知哪里看的”这题有后效性，dp写不了，dfs不知行不行“。结果还真整出来了，样例都过了。可能得记忆化一下？？？

代码：

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=0,ret=0x3f3f3f3f;
int st[1000010];
void dfs(int x){
   if(x==n) {
       ret=ans<ret?ans:ret;
       //cout<<ans<<endl;
       return;
   }
   if(st[x-1]==0&&(x-1)<=n&&(x-1)>=1){
       st[x-1]=1;
       ans++;
       dfs(x-1);
       st[x-1]=0;
       ans--;
   }
   if(st[x+1]==0&&(x+1)<=n&&(x+1)>=1){
       st[x+1]=1;
       ans++;
       dfs(x+1);
       st[x+1]=0;
       ans--;
   }
   if(st[2*x]==0&&x*2<=n&&x*2>=1){
       st[2*x]=1;
       ans++;
       dfs(2*x);
       st[2*x]=0;
       ans--;
   }
}
int main(){
   cin>>n;
   st[1]=1;
   dfs(1);
   cout<<ret;
}