题目名称	1240. [NOIP 2010冲刺十三]迷之阶梯
输入输出	`ladder.in/out`
难度等级	★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	sywgz 于2012-10-30加入
开放分组	全部用户
提交状态
分类标签	动态规划搜索法最短路
	分享题解

通过：88，提交：164，通过率：53.66%
Pine	100	0.000 s	0.00 MiB	C++
waynest	100	0.003 s	0.29 MiB	C++
江羽道	100	0.003 s	0.29 MiB	C++
ztx	100	0.003 s	0.29 MiB	C++
落尘	100	0.003 s	0.32 MiB	C++
waijsf	100	0.003 s	0.67 MiB	Pascal
doge	100	0.004 s	0.29 MiB	C++
天一阁	100	0.004 s	0.29 MiB	C++
ztx	100	0.004 s	0.29 MiB	C++
mikumikumi	100	0.004 s	0.30 MiB	C++

本题关联比赛
20121030
20131014

关于迷之阶梯的近10条评论(全部评论)
广搜完全可以。。数据太小了（pascal逆袭第三）感觉那些大神打的程序那么快，结果我一个菜也能那么快 waijsf 2015-10-07 09:57 10楼
if(k-j>=31) f[i]=min(f[i],f[k]+k-j+1); 为什么你们都不特判，也AC了？是数据太弱了吗 lenibomb 2015-06-12 21:13 9楼
回复 @Makazeu : 不是线性动规吗？跟spfa有啥关系？神利·代目 2015-06-12 19:07 8楼
forever 2015-06-12 18:46 7楼
不是对于所有数据n<=200吗= = 有个n=500的是什么情况 HouJikan 2014-09-07 09:15 6楼
不加return 0 ；就能更快一点，这是什么道理！！！ ztx 2014-06-14 15:43 5楼
终于过了，好水啊！！！！就是一维动规！！！ song 2012-11-02 00:09 4楼
一维动归即可，话说此题虽不难，但本菜交了3次，第一次因为初值赋了maxlongint最后106，第二次是因为看错数据范围，今天狂被水题虐啊~求RP++ 天下第一的吃货殿下 2012-10-31 10:55 3楼
廣度優先搜索(SPFA)無壓力。 Makazeu 2012-10-30 23:06 2楼
奇奇怪怪的“动规”，又有BFS的风采 f[i][j]表示消耗时间为i，在j位置的“蓄力值” Truth.Cirno 2012-10-30 22:33 1楼

1240. [NOIP 2010冲刺十三]迷之阶梯

★ 输入文件：ladder.in 输出文件：ladder.out 简单对比
时间限制：1 s 内存限制：128 MiB

【题目描述】

在经过地球防卫小队的数学家连续多日的工作之后，外星人发的密码终于得以破解。它告诉我们在地球某一处的古老遗迹中，存在有对抗这次灾难的秘密道具。防卫小队立刻派出了一个直升机小分队，迅速赶到了这处遗迹。要进入遗迹，需要通过一段迷之阶梯。登上阶梯必须要按照它要求的方法，否则就无法登上阶梯。它要求的方法有以下三个限制：

1．如果下一步阶梯的高度只比当前阶梯高1，则可以直接登上。

2．除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。

3．当你连续退下k步后，你可以一次跳上不超过$当前阶梯高度+2^k$的阶梯。比如说你现在位于第j步阶梯，并且是从第j+k步阶梯退下来的，那么你可以跳到高度不超过$当前阶梯高度+ 2^k$的任何一步阶梯。跳跃这一次只算一次移动。

开始时我们在第一步阶梯。由于时间紧迫，我们需要用最少的移动次数登上迷之阶梯。请你计算出最少的移动步数。

【输入格式】

第1行：一个整数N，表示阶梯步数。

第2行：N个整数，依次为每层阶梯的高度，保证递增。

【输出格式】

第1行：一个整数，如果能登上阶梯，输出最小步数，否则输出-1。

【样例输入】

5
0 1 2 3 6

【样例输出】

【数据范围】

对于50%的数据：1≤N≤20。

对于100%的数据：1≤N≤200。

每步阶梯高度不超过2^31-1。