Home AcWing 1100 抓住那头牛
Post
Cancel

AcWing 1100 抓住那头牛

Link

BFS 解法需要想清楚几种不可能发生的情况进行剪枝, 否则必定 TLE.

首先, 农夫不可能跳到负数坐标点, 不然只能通过向右跳一步回到 0, 既然这样当初就不该作出这个选择, 反而还多了一步. 因此这种情况必须排除. 而这种情况只可能发生在 cur-1 的时候, 因此在 cur-1 的时候判断. 而每个 cur 我们都是严格保持在 [0,N-1] 内的, 因此 cur-1 只可能小于 cur, 所以不用考虑上界, 只需考虑下界.

刚才解决了坐标点向着变小的方向进行的情况, 现在考虑另外两种, 都是坐标值变大的方向. 注意这里取 N=100010 不是随便取的, 而是要保证能够预留出一定的空间. 例如, 农夫可以两倍跳到一个大于 k 的数, 然后向左走几步就可以到达 k. 那么这个几步也不是随意的, 而是一个确定值. 你想想, 如果先两倍跳、再向左跳, 其实可以转换为先左跳再两倍跳. 但是!!! 这两种方式并不等价, 而是可能相差一个步数! 我先给出几个例子对比:

  • k 是 11, 农夫在 6, 如果先两倍跳到 12, 再向左跳到 11, 需要两步; 如果先向左跳到 5, 再两倍跳到 10, 也需要两步. 此时两种方式可以互换;
  • k 是 12, 农夫在 7, 如果先两倍跳到 14, 再向左跳到 13、12, 需要三步; 如果先向左跳到 6, 再两倍跳到 12, 只需要两步. 此时两种方式相差一步;
  • k 是 13, 农夫在 8, 如果先两倍跳到 16, 再向左跳到 15、14、13, 需要四步; 如果先向左跳到 7, 再两倍跳到 14, 再左跳到 13, 需要三步; 如果一直右跳, 则需要五步. 此时前两种方式相差一步.

所以说, 不要限定只能在 [0,k] 范围跳, 要向右边扩展出一定的空间, 其实 N 取 100002 就可以了 (最大只可能取到 100001, 总范围是 [0,100001], 因此数组长度为 100002). 稍微取大一点肯定没关系.

就刚才说的意思, 我给出一个测试用例拿去测吧:

Input:

1
531 27599

Output:

1
108

所以说上限确定后就好做了啊, visit 函数直接走起. cur+1cur<<1 的时候不能超出 100001, 并且在 cur<<1 之前要确保 cur<k, 以免溢出 (亲测这题数据没卡这个地方, 所以写不写 cur<k 都没关系). 将它写在 cur<<1 之后也可以判断溢出, 那就是 cur<<1 已经计算出来并且溢出了, 但是还是要靠 cur<k 判断. 总之 cur<k 才是判断溢出的主要条件.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=100010;
int n,k;
queue<PII>q;
bool v[N];
void BFS(){
    int cur,num;
    q.push({n,0});
    v[n]=true;
    while(!q.empty()){
        cur=q.front().x,num=q.front().y;
        if(cur==k){
            printf("%d\n",num);
            return;
        }
        q.pop();
        num++;
        if(cur-1>=0&&!v[cur-1]){
            v[cur-1]=true;
            q.push({cur-1,num});
        }
        if(cur+1<N&&!v[cur+1]){
            v[cur+1]=true;
            q.push({cur+1,num});
        }
        if((cur<<1)<N&&cur<k&&!v[cur<<1]){
            v[cur<<1]=true;
            q.push({cur<<1,num});
        }
    }
}
int main() {
    scanf("%d%d",&n,&k);
    BFS();
    return 0;
}

DP 解法:

dp[i] 表示到坐标 i 时总共花费的时间. 开始时先将 dp[i] 初始化为该点到起点的距离的绝对值, 也就是说从起点每次向着该坐标点一步一步地移动需要使用的时间. 显然, 这也正是从 ni 的最大时间.

方案选择:

  • dp[i]: 从 n 朝着单一方向一步一步跳到 i;
  • dp[i-1]: 上一步跳到了 i-1, 从 i-1 向右跳一步到 i;
  • dp[(i+1)>>1]+1:
    • i 为奇数, 从 (i+1)>>1 两倍跳到 i+1, 再从 i+1 向左跳一步到 i;
    • i 为偶数, 从 (i>>1)+1 向左跳一步到 i>>1, 再从 i>>1 两倍跳到 i;
  • dp[i>>1]: i 为偶数, 从 i>>1 两倍跳到 i;

i 为偶数的时候, 不用考虑从 i+1 向左跳到 i 的情况, 因为 i+1 是奇数, 不可能是两倍跳的结果, 除非是两倍跳到 i+2, 再向左跳 2 位, 但这种跳法显然可以被“先左跳 1 位, 再两倍跳”取代 (而且还比这种跳法少了一步); 而 i 是奇数时, i+1 是偶数, 可能是两倍跳的结果, 并且两倍跳后要向左跳一位, 这种跳法满足最小步骤的跳法.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+7;
int n,k,dp[N];
int main(){
    cin>>n>>k;
    for(int i=0;i<=k;i++) dp[i]=abs(i-n);
    for(int i=n+1;i<=k;i++){
        if(i&1) dp[i]=min({dp[i],dp[i-1],dp[(i+1)/2]+1})+1;
        else dp[i]=min({dp[i],dp[i-1],dp[(i+1)/2]+1,dp[i/2]})+1;
    }
    cout<<dp[k]<<endl;
    return 0;
}
This post is licensed under CC BY 4.0 by the author.