【DP】迷之阶梯

Description

思路

DP.

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n,a[201],f[201];
int main(){
	scanf("%d",&n);
	memset(f,0x7f,sizeof(f));     //初始化为一个大的数
	for(int i=1;i<=n;++i)
	  scanf("%d",&a[i]);
	f[1]=0;
	for(int i=2;i<=n;++i)         //要求的点i
	  for(int j=i-1;j>0;--j)      //从j过来
	    for(int jl=1,k=0;k+j<i;jl*=2,++k)  //j从j+k点跳回来，jl可跳距离
	      if(a[j]+jl>=a[i])       //跳的距离够 
	        f[i]=min(f[i],f[j+k]+k+1);  //j+k的步数+跳回来的步数+1
	if(f[n]==f[0]) printf("-1");  //f[0]就是那个很大的数
	else printf("%d",f[n]);
}