Coderforces 1601B. Frog Traveler

发表于 | 分类于 |
字数统计: 494 | 阅读时长 ≈ 2

链接： http://codeforces.com/problemset/problem/1601/B

题意

有一只青蛙掉到了井里 想要跳回到地面上
它在不同的位置具有不同的跳跃高度 可以到达跳跃高度内的任一高度
每次到了一个高度以后，需要休息会下滑一定的距离
求最快跳几次可以跳上地面 并给出每次的路径（每次到的位置为下滑前的位置）

解法

可以把问题抽象成一个最短路径的问题
令dp[i]表示到达高度i所需要花的最少跳跃次数
用par数组存储每次的起跳位置和跳到的位置
用bfs的方式来扩展搜索路径 每次把下滑后的位置插入队列
直到跳跃到地面
回溯par数组找出路径
重点在于需要记录每次的起跳位置和跳到的位置 但是下滑后的位置由队列来进行维护
细节见代码

代码

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
48
49
50
51
52
#include <bits/stdc++.h>
const int MAX = 0x7f7f7f7f;
using namespace std;
queue<int> q;
int n;
pair<int, int> par[300010];
void getPath(int h) {
    if (h == n) return;
    getPath(par[h].first);
    cout << par[h].second << ' ';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    vector<int> a(n + 1), b(n + 1), dp(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
        dp[i] = MAX;
    }
    dp[0] = MAX;
    dp[n] = 0;
    q.push(n);
    int lim = n;
    while(q.size()) {
        int now = q.front();
        q.pop();
        for (int i = now - a[now]; i < lim; i++) {
            // i 是向上跳到的位置 now 是起跳位置
            // i + b[i]是下滑后的位置
            if (dp[i + b[i]] >= MAX) {
                dp[i + b[i]] = dp[now] + 1;
                par[i + b[i]] = {now, i};
                q.push(i + b[i]);
            }
        }
        lim = min(lim, now - a[now]);
    }
    if (dp[0] >= MAX) {
        cout << -1 << endl;
    }
    else {
        cout << dp[0] << endl;
        getPath(0);
    }
    cout << endl;
    return 0;
}