抓牛 dp

1024: 走路还是坐公交

Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 236 Solved: 60
[Submit] [Status] [Web Board] [Creator:Imported]

Description

你收到通知被中南大学录取了，高兴的来到了长沙，很快你就来到了岳麓南路上，已知你的位置是N，中南大学的位置是K。为了去中南大学，你有两种移动方式：走路或者坐公交。

走路：你可以从位置X移动到X+1或者X-1

搭公交车：你可以从位置X移动到2X

每次走路或者搭公交车所需要的时间都是1分钟，你想尽快到达中南大学，所需的时间是多少呢？

Input

多组数据。

对于每组数据，输入一行，分别是N和K(0<=N,K<=100,000)

Output

对于每组数据，输出一行，所需时间

Sample Input

5 17

Sample Output

4


其实这道题就是题面变了一下，就是之前做过的农夫抓牛问题，dp做的

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<string>
 4 #include<cmath>
 5 #include<algorithm>
 6 #include<cstring>
 7 #define MAX_N 100005
 8 #define LL long long
 9 
10 using namespace std;
11 
12 int n,k;
13 int dp[MAX_N];
14 
15 int main()
16 {
17     while(~scanf("%d%d",&n,&k))
18     {
19         if(n >= k)                        // n比k远，只能一步一步往回退 
20              printf("%d
",n-k);
21         else
22         {
23             for(int i = 1; i <= n; ++i)         
24                 dp[i] = n-i;
25             for(int i = n+1; i <= k; ++i)
26             {
27                 if(i%2==0)                //偶数，既可以坐公交也可以+1 
28                 {
29                     dp[i] = min(dp[i/2],dp[i-1])+1;
30                 }
31                 else
32                     if(i%2)                //奇数，可以+1;可以坐公交+1；可以坐公交减1 
33                     {
34                         dp[i] = min(dp[(i+1)/2],dp[(i-1)/2])+2;
35                         dp[i] = min(dp[i-1]+1,dp[i]);
36                     }
37             }
38             printf("%d
",dp[k]);
39         }
40     
41     }
42     return 0;
43 }