linkk
題意:
思路:
代碼:
// Problem: D. Frog Traveler
// Contest: Codeforces - Codeforces Round #751 (Div. 2)
// URL: https://codeforces.com/contest/1602/problem/D
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;typedef unsigned long long ull;
typedef pair<ll,ll>PLL;typedef pair<int,int>PII;typedef pair<double,double>PDD;
#define I_int ll
inline ll read(){ll x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}
#define read read()
#define rep(i, a, b) for(int i=(a);i<=(b);++i)
#define dep(i, a, b) for(int i=(a);i>=(b);--i)
ll ksm(ll a,ll b,ll p){ll res=1;while(b){if(b&1)res=res*a%p;a=a*a%p;b>>=1;}return res;}
const int maxn = 3e5 + 10;
int a[maxn],b[maxn],n,pre[maxn],dis[maxn],ans[maxn];
int mii;
int bfs(){
queue<int>q;
mii=n;
memset(pre,-1,sizeof pre);
memset(dis,0x3f,sizeof dis);
memset(ans,0,sizeof ans);
q.push(n);
dis[n]=0;
while(!q.empty()){
int t=q.front();q.pop();
if(t==0) return dis[t];//跳出井了
for(int x=a[t];x>0;x--){
int now=t-x,tmp=0;//now表示跳了後的點
if(now>=mii) break;//優化
if(now>0) tmp=now,now=now+b[t-x];//維護下滑後的點
else now=0;
//這裡tmp為跳了後的點,now是下滑後的點
if(dis[now]>dis[t]+1){//判斷下滑後的點的步數關系
dis[now]=dis[t]+1;
pre[now]=t;//記錄前驅
ans[now]=tmp;//記下滑前的點
q.push(now);
}
}
mii=min(mii,t-a[t]);//更新最高位置
}
return -1;
}
int main() {
int _=1;
while(_--){
n=read;
rep(i,1,n) a[i]=read;
rep(i,1,n) b[i]=read;
printf("%d\n",bfs());
stack<int>stk;
//列印路徑 倒序輸出
int x=0;
while(pre[x]!=-1){
stk.push(x);
x=pre[x];
}
while(!stk.empty()){
int now=stk.top();
printf("%d ",ans[now]);
// cout<<stk.top()<<" ";
stk.pop();
}
puts("");
}
return 0;
}