P1929 迷之阶梯

    • 252通过
    • 790提交
  • 题目提供者 JOHNKRAM
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp
  • 难度 普及/提高-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

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

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

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

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

    输入输出格式

    输入格式:

    第一行:一个整数 N,表示阶梯步数。

    第二行:N 个整数,依次为每层阶梯的高度,保证递增。

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    5
    0  1  2  3  6 
    
    输出样例#1: 复制
    7

    说明

    【样例解释】

    连续登 3 步,再后退 3 步,然后直接跳上去。

    【数据范围】

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

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

    对于 100%的数据:每步阶梯高度不超过 2^31-1

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。