/ Vijos / 题库 /

教主的游乐场

教主的游乐场

描述

Orz教主的成员为教主建了一个游乐场,在教主的规划下,游乐场有一排n个弹性无敌的跳跃装置,它们都朝着一个方向,对着一个巨大的湖,当人踩上去装置可以带你去这个方向无限远的地方,享受飞行的乐趣。但是等这批装置投入使用时,却发现来玩的人们更喜欢在这些装置上跳来跳去,并且由于这些装置弹性的优势,不但它们能让人向所对的方向能跳很远,也都能向相反方向跳一定的距离。

于是教主想出了个游戏,这n个装置按朝向相反的方向顺序以1..n编号。第i个装置可以跳到1..i-1个装置,且每个装置有一个不一定相同的反方向弹性a[i],代表第i个装置还可以跳到第i+1..i+a[i]个装置。教主指定一个起始的装置,问从这个装置开始,最少需要连续踩几次装置(起始的装置也算在内),可以跳到第n个装置的后方,即若第k个装置有k+a[i]>n,那么从第k个装置就可以跳到第n个装置的后方。

(PS:你可以认为有n+1个装置,即需要求多少次能条到第n+1个装置)

格式

输入格式

输入的第1行包含两个正整数n,m,为装置的数目以及询问的次数。

第2行包含n个正整数,第i个正整数为a[i],即第i个装置向反方向最大跳跃的长度。

第3行包含了m个正整数,为询问从哪一个装置开始,最少要几次跳到第n个的后方。

数字之间用空格隔开。

输出格式

输出包含1行,这一行有m个正整数,对于每一个询问,输出最少需要踩的装置数,数字之间用空格隔开。

行末换行且没有多余的空格。

样例1

样例输入1

5 5
2 4 1 1 1
1 2 3 4 5

样例输出1

2 1 2 2 1

限制

对于20%的数据,有n≤10;
对于40%的数据,有n≤100,m≤10;
对于60%的数据,有n≤1000,a[i]≤1000,m≤500;
对于100%的数据,有n≤100000,a[i]≤n,m≤40000。

时限1s

提示

若从第1个装置开始则跳到第2个装置,接着就可以跳到第n个装置的后方。

若从第3个装置开始则同样跳到第2个装置。

若从第4个装置开始可以跳到第2个装置或最后一个装置,接着跳出第n个装置,答案同样为2。

信息

ID
1471
难度
6
分类
动态规划 | 单调性DP 点击显示
标签
递交数
782
已通过
207
通过率
26%
被复制
1
上传者

相关

在下列训练计划中:

RP++分类题库

在下列比赛中:

Orz教主第三次模拟赛