vijosP1471 教主的游乐场

时间:2024-06-08 20:06:02

vijosP1471 教主的游乐场

链接:https://vijos.org/p/1471

【思路】

递推。

首先找到最左边的可以一步跳到后方的L,

那么L之后的点有两种情况:要么a足以跳到后方步数为1,要么可以一步调到L有L跳到后方步数为2。

对于L之前的点而言,再进行相同的操作,相当于代码中缩小R为L。

【代码】

 #include<iostream>
#include<cstdio>
using namespace std; const int maxn = +; int n,q;
int a[maxn],step[maxn]; inline int read_int(){
char c=getchar();
while(!isdigit(c)) c=getchar();
int x=;
while(isdigit(c)) {
x=x*+c-'';
c=getchar();
}
return x;
} int main() {
ios::sync_with_stdio(false);
n=read_int(); q=read_int();
for(int i=;i<=n;i++) a[i]=read_int(); int L=,R=n+;
step[R]=;
do{
int i=;
while(i+a[i]<R) i++;
for(int j=i;j<R;j++)
if(j+a[j]>=R) step[j]=step[R]+;
else step[j]=step[R]+;
R=i;
}while(R>);
int x;
for(int i=;i<=q;i++) {
x=read_int();
cout<<step[x];
if(i<q) cout<<" ";
else
cout<<"\n";
}
return ;
}