一发st表
仅供参考（不建议操作本题）
看下就行了
#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
int dp[200005][105],a[200005],ans,LOG[200005];
int f[200005][50];
int n,q;

int main()
{
scanf("%d%d",&n,&q);
for(int i=2;i<=n;i++)
LOG[i]=LOG[i/2]+1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
dp[i][0]=a[i]+i;
}
// for(int i=n;i>=1;i--)
// {
// ans[i]=ans[i+a[i]]+1;
// }
//get_st();
int l,r,d,t;
l=1;
memset( f, 125 ,sizeof ( f ));
for (int i=1;i<MAXN;i++)
for (int j=0;j<=20;j++ )
if ( i+(1<<j)-1 >n )
f[i][j]=0;
for (int i=n;i>=1;i--)
{
int d=LOG[a[i]];
f[i][0]=min( f[i+1][d] , f[i+a[i]-(1<<d)+1][d] )+1;
for (int j=1;(1<<(j-1))+i<=n;j++)
f[i][j]=min( f[i][j-1] , f[ i+(1<<(j-1))][ j-1 ] );
}

int MIN=f[1][0];
for (int i=2;i<=n;i++)
{
f[i][0]=min( f[i][0] , MIN+1 );
MIN=min( MIN , f[i][0] );
}

for(int i=1;i<=q;i++)
{
l=1;
ans=1;
scanf("%d",&r);
printf("%d",f[r][0]);
if(i!=q) printf(" ");
}
}
O（nlogn + m）

O(N) 算法：

首先从右向左找到最左边的能一步到达n+1点的点 设这个点为I，以这个I点为左边界，以n点为右边界，这个区间内的点只有两种情况：1.如果能直接跳到n+1点 那么步数为1；2.否则步数为二（跳到I点然后到n+1点）；然后以I-1点为右边界，继续向左找能一步到达I点的最左边的点，设为点J 那么区间（J,I-1）内的点也只有两种情况：1.如果能跳到I点 那么步数为 I点的步数+1，2.如果跳不到，那么步数为I点步数+2（先跳到J点，再跳到I点）

以此类推，直到扫到左边界 复杂度O（n）；

#include <map>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <sstream>
#include <iostream>
#include <algorithm>
#define maxn (100000 + 50)
#define inf 0x3f3f3f3f
#define pi acos(-1.0)
using namespace std;
typedef long long int LLI;

int a[maxn],maxs[maxn];
int dp[maxn];

int main() {
//    freopen("re.txt","r",stdin);
//    freopen("out44.txt","w",stdout);
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i ++) {
        scanf("%d",&a[i]);
        a[i] = a[i] + i;
        if(i == 1)  maxs[i] = a[i];
        else maxs[i] = max(maxs[i - 1],a[i]);
    }
    int r = n;
    do {
        int p = upper_bound(maxs + 1,maxs + n + 1,r) - maxs;
        for(int i = p; i <= r; i ++) {
            if(a[i] > r)    dp[i] = dp[r + 1] + 1;
            else            dp[i] = dp[r + 1] + 2;
        }
        r = p - 1;
    } while(r > 0);
    for(int i = 1; i <= m; i ++) {
        int que;
        scanf("%d",&que);
        if(i < m)   printf("%d ",dp[que]);
        else        printf("%d\n",dp[que]);
    }
    return 0;
}

复杂度算低的了吧

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1728 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1728 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 1732 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1728 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1728 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1732 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1736 KiB, score = 10
测试数据 #7: Accepted, time = 46 ms, mem = 1732 KiB, score = 10
测试数据 #8: Accepted, time = 31 ms, mem = 1732 KiB, score = 10
测试数据 #9: Accepted, time = 46 ms, mem = 1728 KiB, score = 10
Accepted, time = 138 ms, mem = 1736 KiB, score = 100

感谢liu932073956的题解，跪膜
```c++
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int n,m;
int a[100005];
int Right;
int ans[100005];

int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i];
Right=n;
do
{
int k;
for(k=1;k+a[k]<=Right;k++);
for(int i=k;i<=Right;i++)
{
if(a[i]+i>Right)
ans[i]=ans[Right+1]+1;
else
ans[i]=ans[Right+1]+2;
}
Right=k-1;
}
while(Right>0);
for(int i=1;i<=m;i++)
{
int l;
cin>>l;
cout<<ans[l];
if(i!=m)
cout<<" ";
}
return 0;
}
```

赞 liu932073956 的题解，非常巧妙地利用了这题的单调性。40行AC代码：

#include <stdio.h>
#define MAX_NUM 100000

int dist[MAX_NUM]; //从i出发能往后跳的距离
int step[MAX_NUM]; //记录到达num的最小步数

int main(){
int num, numQuery;
int i, right, left, query;

scanf("%d %d", &num, &numQuery);
for(i=0; i<num; i++)
scanf("%d", &dist[i]);

right = num;
step[num] = 0; //初始化
do{
//规定：left是最左边的能直接到达right的点
//显然有：left~right-1之间的点只需1~2次即可到达right（要么直达，要么折回left再直达）
for(i=0; i+dist[i]<right; i++); //找到left的位置
left = i;
for(; i<right; i++){
if(i+dist[i]>=right)
step[i] = step[right]+1; //直达right，步数+1
else
step[i] = step[right]+2; //跳回left后再直达right，步数+2
}
right = left;
}while(right>0); //重复操作直至区间被分完

for(i=0; i<numQuery; i++){
scanf("%d", &query);
printf("%d", step[query-1]);
if(i<numQuery-1)
putchar(' ');
else
putchar('\n'); //特殊处理，因为不能有多余空格
}
return 0;
}

Wa 和 运行时…… 跪求大神解

Program p1417;
Var i,j,k,m,n:longint;
q,p:boolean;
a,f,t1:array[1..1000000] of longint;
t2:array[1..1000000] of 0..1;
d:array[1..40000] of longint;

Procedure inputbox;
begin
readln(n,m);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to m do
read(d[i]);
end;

Procedure work;
begin
fillchar(t2,sizeof(t2),0);
fillchar(f,sizeof(f),0);
j:=0;
q:=false; p:=true;
for i:=1 to n do
begin
if a[i]+i>n then
begin
f[i]:=1;
if not q then j:=i;
q:=true;
end else
if q then f[i]:=2 else p:=false;
end;
q:=false;
if not p then
for i:=j downto 1 do
begin
if a[i]+i>n then
k:=i else
begin
if a[i]+i>=k then f[i]:=2 else
f[i]:=1+f[i+a[i]];
end;
end;
end;

Procedure print;
begin
for i:=1 to m-1 do
write(f[d[i]],' ');
writeln(f[d[m]]);
end;

Begin
inputbox;
work;
print;
End.

---|---|---|---|-昏割线---|---|-

手滑打错了个东西

我们先想寻找一个最靠左的可以蹦出N的点a，a右边的点i如果能跳出N那么d[i]:=d[n+1]+1 else d[i]:=d[a]+1;处理一遍后再将n：=a-1,如此循环虐杀线段树

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

program ex;

var i,j,n,m:longint;

left,right,ans:array[1..100000]of longint;

procedure init;

var i,j,x:longint;

begin

readln(n,m);

for i:=1 to n do

begin

read(x);

left[i]:=i;

right[i]:=i+x;

end;

end;

procedure qsort(l,r:longint);

var i,j,mid,temp:longint;

begin

i:=l;j:=r;mid:=right[(l+r) shr 1];

repeat

while right[i]mid do dec(j);

if ij;

if i

Orz 普及组加强版 大牛！

JP算法！Orz! OTL!

我想太复杂了.

囧~~~~

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

太搓了！交了5次！一直不相信是程序错.....每次都70....

注意！第8个点排序要注意！它可能会让你的快排挂掉！

最后又来个忘了writeln，我囧~~~~

AC率啊！后来人千万别重蹈覆辙

惭愧啊

我不会线段树

多亏了有题解.. O(n)的

OIBH上的

教主的游乐场(park) 排序，贪心

无论从哪个装置开始，若要跳跃次数最少，最多向左跳1次，并且这1次是在一开始跳的，因为如果向右跳后再向左跳，那么显然这次向左能跳到的装置前面也可以跳到。那么每次跳跃则要选择一个能让下一步跳到的位置编号尽量大的装置，因为跳到第i个装置，它下一次的行动范围为[1, i+a[i]]，所以显然要i+a[i]得到最大。这样可以得到60%的分数。

正因为每次选择一个能让下一步跳到的位置编号尽量大的装置总可以得到最优解，对于每个装置，下一步能跳到的装置编号为i+a[i]（称之为右边界），那么若按右边界排序从大到小排序后，每个装置为起点的答案就会是不下降的。若在k步能到达的装置里面选一个装置编号最小的i，那么对于k步内不可达的装置，若右边界大等于i，那么它即为k+1步可达的，同样在里面选出个编号最小的。由于可以向左无限跳，所以不必考虑左边界。1步可达的编号为n+1。

PS：抽象模型，每个装置变成区间[i, i+a[i]]，问题就变成了区间覆盖的变种。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

o(╯□╰)o 这道题为什么要用 二分 or 线段树 捏

为什么我只想得到DP。。。。。

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 9ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

sunny 评的

每次至多往回跳一次

还要打个2分

大牛用nlogn啊（我反正不会线段树），其实O(n)就可以

先按i+a[i]为关键字快排一遍，

设个min记录至少k步就能到n+1的点中的最小编号，

i+a[i]>=min的一定可以先到min在到n+1，所需步数为k+1，

然后更新min（为k+1步时最小的 i）

我讲不清楚，核心代码自己看吧：

Procedure Main; //b[i]=i+a[i]; c[i]=i;

Begin //num[i]记录i至少要几步到n+1

Quicksort(1,n);

i:=n; Min:=n+1; k:=0;

While i>0 Do

Begin

j:=Min; Inc(k);

While b[i]>=j Do Begin

Num[c[i]]:=k;

If c[i]

汗...数组开太小了...2次才AC...

动规+线段树优化 O(nlogn)

核心代码：

for i:=n downto 1 do begin

if i+a[i]>n then f[i]:=1

else f[i]:=min(i+1,i+a[i],1)+1;

update(i,f[i],1);

end;

for i:=1 to m do begin

read(k);

if k>1 then begin

ans:=min(1,k-1,1)+1;

if f[k]

贪心O（N)

求教O(n)的算法……

我只会O(nlogn)的，还用了线段树……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

没有抄std

var

i,j,k,n,m,x,y:longint;

a,f,b:array[1..100000]of longint;

procedure ll(p,q:longint);

var

i:longint;

begin

for i:=p+1 to q-1 do

if ((i+a[i]>=q)and(yn))or((i+a[i]>q))

then f[i]:=f[p]

else f[i]:=f[p]+1;

end;

begin

readln(n,m);

for i:=1 to n do

read(a[i]);

readln;

for j:=1 to m do

read(b[j]);

y:=n;

k:=n;

fillchar(f,sizeof(f),0);

f[n]:=1;

for i:=1 to n do

begin

if i+a[i]>n

then begin

x:=i;

f[x]:=1;

k:=x;

ll(x,y);

break;

end;

end;

repeat

y:=k;

for i:=1 to y-1 do

begin

if i+a[i]>=y

then begin

x:=i;

f[x]:=f[y]+1;

ll(x,y);

break;

end;

k:=x;

end;

until f[1]0;

for i:=1 to m-1 do

write(f[b[i]],' ');

write(f[b[m]]);

end.

大牛们

为什么我第8个点 超了?

别的都秒杀啊!

顺便问下 怎么优化?

感激不尽!!!!!!