链接：https://ac.nowcoder.com/acm/contest/5968/A

题目描述

牛市，一个拥有悠久历史的城市，2333年考古学家在牛市发现了一个神秘的遗迹，这些勇敢而智慧的古队员准备进入这个遗迹，但要进入这个遗迹就需要通过一段天梯。而登上天梯必须要按照它要求的方法，否则就无法登上。它要求的方法为：

1．可以直接登上比当前位置高1个单位高度的天梯。

2．可以从当前阶梯往下退一级天梯（第一级天梯除外）。

3．在连续退k步后，跳跃一次，跳跃的高度不超过2^k。比如说你现在位于第i级天梯，且之前从第i+k级天梯退下来，此时你可以跳到高度不超过(当前高度+ 2^k)的任何一级天梯。每一次跳跃只算一次移动哦！

开始的时候考古小队在第一级天梯。请你计算出最少的移动步数以登上最高一级天梯。

为何考古搞得跟游戏历险一样？牛市一定是一个魔性的城市！

输入描述:

第1行：一个整数N，表示天梯级数。

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

输出描述:

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

示例1
输入
5
0 1 2 3 6
输出
7

#include<iostream>
#include<string.h>
#include<stdio.h>
using namespace std;
int a[205],dp[205];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    memset(dp,0x3f,sizeof(dp));
    dp[1]=0;
    for(int i=2;i<=n;i++){
        if(a[i]-a[i-1]==1){
            dp[i]=min(dp[i],dp[i-1]+1);
        }//如果上下两天梯高度差为1，那么就可以直接走到，所以取步数小的即可
        for(int k=1;k<i;k++){
            int now=i-k;//退了k步后的位置 
            int s=1<<k;//从退了k步的位置最多可以向上多少步 
            int x=1;
            while(x<n&&a[x+1]<=a[now]+s){
                ++x;
            }//看从当前位置最高可以到那个阶梯 
            dp[x]=min(dp[x],dp[i]+k+1);
        }//枚举从当前高度退到第一节天梯的所有情况 
    }
    if(dp[n]<1e7){
        cout<<dp[n];
    }
    else{
        cout<<-1;
    }
    return 0;
}