오래된 우 시장, 유적지 의 사다리.

오래된 소 시장, 유적지 의 사다리 시간 제한: C / C + + 1 초, 기타 언어 2 초 공간 제한: C / C + + 262144 K, 기타 언어 524288 K 64bit IO Format:% lld 제목 설명
우 시 는 유구 한 역 사 를 가 진 도시 로 2333 년 고고학자 들 이 우 시 에서 신비 로 운 유적 을 발견 했다. 이런 용감 하고 지혜 로 운 고대 대원 들 은 이 유적 에 들 어 갈 준 비 를 하지만 이 유적 에 들 어 가 려 면 하늘 사다 리 를 통과 해 야 한다.사다리 에 오 르 려 면 그 방법 에 따라 야 한다. 그렇지 않 으 면 올 라 갈 수 없다.그것 이 요구 하 는 방법 은:

1．            1        。

2．              （       ）。

3．    k  ，    ，        2^k。         i   ，     i+k      ，            (    + 2^k)       。            ！

처음에 고고학 소대 가 1 급 사다리 에 있 었 다.가장 높 은 계단 에 오 르 기 위해 최소한 의 이동 보 수 를 계산 해 보 세 요.
왜 고고학 은 게임 모험 처럼 만 들 었 습 니까?우 시 는 틀림없이 마 성의 도시 일 것 이다!입력 설명:
첫 번 째 줄: 하나의 정수 N 은 사다리 급 수 를 나타 낸다.
두 번 째 줄: N 개의 정 수 는 각 층 의 사다리 의 높이 로 점차 증가 할 것 을 보증한다.
출력 설명:
하나의 정수, 사다리 에 올 라 갈 수 있다 면 최소 걸음 수 를 출력 합 니 다. 그렇지 않 으 면 출력 - 1.
예제 1 입력 복사
5 0 1 2 3 6
출력 복사
7
설명 하 다.
1≤N≤2001 \leq N \leq 2001≤N≤200。 각 계단 의 높이 는 231 - 12 ^ {31} - 1231 - 1 을 초과 하지 않 습 니 다.

#include
#include
#include
#include
using namespace std;

long long f[60],dp[205],s[205];
int main()
{
	int n;
	f[0] = 1;
	for (int i = 1; i <= 42; i++)
	{
		f[i] =f[i-1]* 2;
	}
	for (int i = 1; i <= 205; i++)
		dp[i] = 1e16;
	
	cin >> n;
	dp[1] = 0;
	for (int i = 1; i <= n; i++)
		cin >> s[i];
	for (int i = 2; i <= n; i++)
		for (int j = i-1; j >0; j--)
		{
			if (s[i] - s[j] == 1)
				dp[i] = dp[j] + 1;
			else {
				
				for (int k = j-1; k >0&&k>j-31; k--)
				{
					
					if (s[i] - s[k] <= f[j - k])
					{
						dp[i] = min(dp[i], dp[j] + j - k + 1);
					
					}
				}
			}
		}
	if (dp[n] >= 1e16/2)
		dp[n] = -1;
	cout << dp[n] << endl;

}

#pragma GCC optimize(2)
#include
#define ll long long
#define maxn 1005
#define inf 1e9
#define pb push_back
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
 
inline ll read()
{
	ll x=0,w=1; char c=getchar();
	while(c<'0'||c>'9') {if(c=='-') w=-1; c=getchar();}
	while(c<='9'&&c>='0') {x=(x<<1)+(x<<3)+c-'0'; c=getchar();}
	return w==1?x:-x;
}
const int N=2e2+10;
ll a[N],dp[N],f[N];
int n;
int main()
{
    f[0]=1;rep(i,1,40) f[i]=f[i-1]*2;
 
    n=read(); rep(i,1,n) a[i]=read(),dp[i]=1e14;
 
 
    dp[1]=0;
    for(int i=2;i<=n;++i){
 
        int flag=0;
        for(int j=i-1;j>=1;--j){
 
            for(int k=0;k<i-j&&k<41;++k){
                if(a[j]+f[k]>=a[i]){
 
                    dp[i]=min(dp[i],dp[j+k]+k+1);
                    flag=1;
                }
            }
 
        }
 
 
        if(!flag) {puts("-1");return 0;}
    }
 
    printf("%d
",dp[n]);
 
 
}
/*
5
0 1 2 3 100
*/