记录编号	49838	评测结果	AAAAAAAAAA
题目名称	1240.[NOIP 2010冲刺十三]迷之阶梯	最终得分	100
用户昵称	fanzeyi	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2012-11-09 16:15:21	内存使用	1.96 MiB

#include <cstdlib>
#include <cstring>
#include <cstdio>
#define MAX 200

unsigned long long int height[MAX]; 
int n; 
int f[MAX]; 
unsigned long long int sqr[33] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296}; 


int fmin(int a, int b) {
    return a < b ? a : b; 
}

int main() {
    FILE *fin = fopen("ladder.in", "r"); 
    FILE *fout = fopen("ladder.out", "w"); 
    memset(f, 0x7F, sizeof(f)); 
    fscanf(fin, "%d", &n); 
    for(int i = 0; i < n; i++) {
        fscanf(fin, "%lld", &height[i]); 
    }
    f[0] = 0; 
    for(int i = 1; i < n; i++) {
        if(height[i] - 1 == height[i - 1]) {
            // height + 1
            f[i] = fmin(f[i], f[i-1] + 1); 
        }
        for(int j = 0; j < i; j++) {
            for(int k = j + 1; k < i; k++) {
                if(height[j] + sqr[k - j] >= height[i]) {
                    f[i] = fmin(f[i], f[k] + (k - j) + 1); 
                }
            }
        }
    }
    if(f[n-1] == 0x7F7F7F7F) {
        fprintf(fout, "-1\n"); 
        return 0; 
    }
    fprintf(fout, "%d", f[n-1]); 
    return 0; 
}