记录编号	47130	评测结果	AAAAAAAAAA
题目名称	1240.[NOIP 2010冲刺十三]迷之阶梯	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2012-10-30 22:02:17	内存使用	1.96 MiB

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 200 + 10, M = 33, INF = 0x7ffffff;
typedef long long int int64;
int n, f[N];
int64 h[N], p[M] = {1};
int main() {
    freopen("ladder.in", "r", stdin);
    freopen("ladder.out", "w", stdout);
    for(int i=1; i<M; i++)
        p[i] = p[i-1] << 1;
    scanf("%d", &n);
    for(int i=1; i<=n; i++)
        scanf("%lld", h+i);
    fill(f, f+n+1, INF);
    f[1] = 0;
    if(h[2] - h[1] != 1) {
        printf("%d\n", -1);
        return 0;
    } f[2] = 1;
    for(int i=3; i<=n; i++)
        for(int j=1; j<i; j++)
            for(int k=1; k<=j; k++)
                if(h[i] - h[k] <= p[j - k])
                    f[i] = min(f[i], f[j] + j - k + 1);
    printf("%d\n", f[n] == INF ? -1 : f[n]);
    return 0;
}