Frog Traveler(思维/bfs/线段树)

题目 官方题解

题意：青蛙掉进井了，它要跳出坑。现在青蛙在深度为n的坑中。它在深度i的坑，最多能向上跳跃 a i a_i ai​的高度；当青蛙跳到新的位置i，由于摩檫力和体力消化等因素，它会往后滑 b i b_i bi​。现在青蛙从位置n，要跳到地面（位置0），问最小需要跳多少次，并输出路径。如果跳不出（跳不出也太难了233），输出（-1）。

思路：广搜，每次入队的点都是下滑前的位置。为保证线性复杂度，维护最近的跳跃点lst。

#include  
using namespace std;
const int maxn = 300010;

int n;
int a[maxn], b[maxn], c[maxn];
int pre[maxn], vis[maxn];

vector ans;
void cal_ans(int k) {
//	printf("k :%d\n", k);
	while (pre[k] != -1) {
		ans.push_back(k);
		k = pre[k];
	}
}
void print_ans() {
	int sz = ans.size();
	printf("%d\n", sz);
	for (int i = sz - 1; i > 0; --i) {
		printf("%d ", ans[i]);
	}
	printf("%d\n", ans[0]);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i >1;
		if(y