【题解】抓奶牛

题目描述

  有人通知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;
} 
参考程序

 

上一篇:POJ 2318 TOYS (计算几何+叉积)


下一篇:洛谷 P1879 [USACO06NOV]玉米田Corn Fields