D. Frog Traveler

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

题意

青蛙跳进了一个深度为n的井里
不同的深度青蛙最多可以跳ai的高度(0~a[i])
每次跳跃后要休息一下
在不同的深度休息会往下掉b[i]
要求 如果能够出到井外
求最小跳跃次数和路径
如果不能
输出-1

思路

暴力直接想到bfs
但是需要细节
不然会T

AC代码

#include <bits/stdc++.h>
#define endl "\n" 
#define INF 0x3f3f3f3f3f3f3f3f
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
using namespace std;
typedef long long ll;
const  ll mod = 1000000007;
const   double  PI = acos(-1.0);
const double EI = exp(1.0);
const int  N = 300050;
const int maxn = 2 * N;
const double  eps = 1e-8;
int a[N], b[N], v[N];
int ans[N];
ll dp[N];
int vis[N], pre[N];
void bfs(int n)
{
	int x=n;
	queue<int>q;
	for (int i = 1; i <= n; i++)
		dp[i] = maxn,pre[i]=i;
	dp[x] = 0;
	vis[x] = 1;
	q.push(x);
	int last = n; //关键点就在于这个last 其代表目前青蛙能跳到的最接近0的地方
	while (!q.empty())
	{
		if (vis[0])break;
		x = q.front();
		q.pop();
		int v =x+b[x];
		for (int i=min(v,last-1); i >= v - a[v]; i--)//主要目的就是在这剪枝
		{
			if (vis[0])break;
			if (vis[i])continue;
			if (!vis[i] && dp[i] > dp[v] + 1)
			{
				vis[i] = 1;
				dp[i] = dp[x] + 1;
				pre[i] = x;
				q.push(i);
			}
		}
		last = min(last, v - a[v]);
	}

}
void solve()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i <= n; i++)
	{
		cin >> b[i];
	}
	for (int i = 0; i <= n; i++)
		dp[i] = maxn;
	bfs(n);
	if (dp[0] == maxn)
		cout << -1 << endl;
	else
	{
		cout << dp[0] << endl;
		int tot = 0;
		int q = 0;
		while (pre[q]!=q)
		{
			ans[++tot] =q;
			q = pre[q];
		}
		for (int i = tot; i >= 1; i--)
			cout << ans[i] << " ";
		cout << endl;
	}
}
int main()
{
	std::ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	//int t; cin >> t; while (t--)
	solve();
	return 0;
}