B. Frog Traveler

解法1 单调性优化BFS

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 5;
int a[N], b[N], qq[N], d[N], pre[N], pre_b[N];
int main() {
    int n; cin >> n;
    for(int i = 1; i <= n; i ++) cin >> a[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];
    int mn = n + 1;
    memset(d, 0x3f, sizeof d);
    int hh = 0, tt = -1;
    qq[++ tt] = n; d[n] = 0;
    while(hh <= tt) {
        auto t = qq[hh ++];
        // t -> i -> i + b[i]
        for(int i = t - a[t]; i <= t && i < mn ; i ++) {
            if(d[i + b[i]] == 0x3f3f3f3f) {
                d[i + b[i]] = d[t] + 1;
                qq[++ tt] = i + b[i];
                pre_b[i + b[i]] = i; pre[i] = t;
            }
        }
        mn = min(mn, t - a[t]);
    }
    if(d[0] == 0x3f3f3f3f) {
        cout << -1 << endl;
        return 0;
    }
    cout << d[0] << endl;
    int now = 0;
    vector<int> ret;
    while(now != n) {
        ret.push_back(pre_b[now]);
        now = pre[pre_b[now]];
    }
    reverse(ret.begin(), ret.end());
    for(auto &it: ret) cout << it << ' ';
}

解法2 线段树辅助建图