在经过地球防卫小队的数学家连续多日的工作后，外星人发的密码终于得以破解。它 告诉我们在地球某一处的古老遗迹中，存在有对抗这次灾难的秘密武器。防卫小队立即赶 到这处遗迹。要进入遗迹，需要通过一段迷之阶梯。登上阶梯必须要按照它要求的方法， 否则就无法登上阶梯。它要求的方法有以下三个限制：1.如果下一步阶梯的高度只比当前阶梯高 1，则可以直接登上。2.除了第一步阶梯外，都可以从当前阶梯退到前一步阶梯。3.当你连续退下 k 后，你可以一次跳上不超过当前阶梯高度 2^k的阶梯。比如说你现 在位于第 j 步阶梯，并且是从第j+k 步阶梯退下来的，那么你可以跳到高度不超过当前阶梯高度+ 2^k的任何一步阶梯。跳跃这一次只算一次移动。开始时我们在第一步阶梯，由于时间紧迫，我们需要用最少的移动次数登上迷之阶梯。 请你计算出最少的移动步数。输入输出格式输入格式：第一行：一个整数 N，表示阶梯步数。第二行：N 个整数，依次为每层阶梯的高度，保证递增。输出格式：第一行：一个整数，如果能登上阶梯，输出最小步数，否则输出-1。输入输出样例输入样例#1： 50 1 2 3 6 输出样例#1： 7说明【样例解释】连续登 3 步，再后退 3 步，然后直接跳上去。【数据范围】对于 50%的数据：1≤N≤20。对于 100%的数据：1≤N≤200。对于 100%的数据：每步阶梯高度不超过 2^31-1
f[i]表示走到h[i]的最少步数
那么转移方程就出来了
if h[i]==h[i-1] f[i]=min(f[i],f[i-1]+1)
else j->i 假设需要h[j]+2^k
则 f[i]=min(f[i],f[j+k]+k+1)
还要注意无解的情况
1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #define ll long long 8 #define DB double 9 using namespace std;10 inline ll read()11 {12 ll x=0,w=1;char ch=getchar();13 while(!isdigit(ch)){ if(ch=='-') w=-1;ch=getchar();}14 while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();15 return x*w;16 }17 int n,tmp;18 ll h[300],f[300];19 int main()20 {21 n=read();22 for(int i=1;i<=n;++i) h[i]=read(),f[i]=1e9;23 f[1]=0;24 for(int i=2;i<=n;++i)25 {26 if(h[i]==h[i-1]+1) h[i]=h[i-1]+1;27 for(int j=1;j