题目描述
有人通知Farmer John他的逃跑的奶牛的位置,FJ要立即把它抓回来。他现在位于点N(0≤N≤100000),而奶牛位于跟他同一直线上的点K(0≤K≤100000)。Farmer John有两种方法去抓住奶牛:走或传。
走:Farmer John能从点X走到X-1或X+1的位置,用时一分钟。
传:Farmer John能从点X到2X的位置,用时一分钟。
如果奶牛在原地不动,问FJ至少要多少分钟才能抓住奶牛。
输入格式
一行,两个整数,N和K。
输出格式
一行,为Farmer John抓住奶牛用的最少时间。
输入样例
5 17
输出样例
4
样例说明
抓住奶牛最快的路径是5-10-9-18-17,用时4分钟。
题解
容易想到,如果往前走一步,下一步就不应该再走一步。
我们刚开始先把往后走的情况预处理出来,然后开始dp即可。具体参考下面给出的代码。
#include <iostream> #include <algorithm> #include <cmath> #include <cstring> #define INF 2139062143 #define MAXN 200001 using namespace std; int n, k; int f[MAXN][3]; int ans; int main() { cin >> n >> k; if(n > k) return cout << n - k, 0; memset(f, 127, sizeof f); for(register int i = n - 1; i >= n / 2; i--) { f[i][2] = n - i; f[i * 2][0] = f[i][2] + 1; } f[n][0] = f[n][1] = f[n][2] = 0; for(register int i = n; i <= k; i++) { if(i != n) { f[i][1] = min(f[i - 1][0], min(f[i - 1][1], f[i - 1][2])) + 1; f[i][2] = min(f[i][2], min(f[i + 1][0], min(f[i + 1][1], f[i + 1][2])) + 1); } f[i * 2][0] = min(f[i][0], min(f[i][1], f[i][2])); if(f[i * 2][0] != INF) { f[i * 2][0]++; for(register int j = i * 2 - 1; j > i; j--) { if(f[j][2] <= f[i * 2][0] + i * 2 - j) break; else f[j][2] = f[i * 2][0] + i * 2 - j; } } //cout << i << " " << f[i][0] << " " << f[i][1] << " " << f[i][2] << endl; } ans = min(f[k][0], min(f[k][1], f[k][2])); cout << ans; return 0; }参考程序