[练习赛]DP--A题

https://ac.nowcoder.com/acm/contest/5968/A
登上天梯必须要按照它要求的方法，否则就无法登上。它要求的方法为：
1．可以直接登上比当前位置高1个单位高度的天梯。
2．可以从当前阶梯往下退一级天梯（第一级天梯除外）。
3．在连续退k步后，跳跃一次，跳跃的高度不超过2^k。比如说你现在位于第i级天梯，且之前从第i+k级天梯退下来，此时你可以跳到高度不超过(当前高度+ 2^k)的任何一级天梯。每一次跳跃只算一次移动哦！
开始的时候考古小队在第一级天梯。请你计算出最少的移动步数以登上最高一级天梯。

往后退k步，一定是选能跳到的最高的阶梯才能使得步数最少（题目说可以跳到任意一级是迷惑）
dp[i] 表示跳到第i级阶梯的最小步数
状态转移显而易见：
i枚举后退k步：mxHei--能挑到的最高高度

//往后退k步，一定是选能跳到的最高的阶梯才能使得步数最少（题目说可以跳到任意一级是迷惑）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MYINTMAX 0x3f3f3f3f
#define N 205
int a[N],dp[N];//dp[i] 跳到第i级阶梯的最小步数
int main()
{
    int n;cin>>n;
    for(int i=1;i<=n;++i) {
        cin>>a[i];
        dp[i]=MYINTMAX;
    }
    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);
        //cout<<dp[i]<<endl;
        for(int k=1;k<i;k++){  // 枚举所有后退的可能性
            int jump = 1<<k;
            int mxHei=i-k;
            while(mxHei<n && a[mxHei+1]<=a[i-k]+jump){  // 找到能到的最高阶梯---
                mxHei++;
            }
            dp[mxHei] = min(dp[mxHei],dp[i]+k+1);
        }
    }
    if(dp[n]>=MYINTMAX) cout<<-1;
    else cout<<dp[n];
}