记录编号	47154	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]迷之阶梯	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.021 s
提交时间	2012-10-30 23:05:27	内存使用	0.29 MiB

#include <cstdio>
#include <cstdlib>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
typedef unsigned int usint;
const usint MAXN=222;
usint INF,ichi=1; bool flag[MAXN]={0};
usint F[MAXN],N,H[MAXN],bny[MAXN]={1};
queue<usint> q;

inline void init()
{
	cin>>N;
	if(N==ichi) {printf("0\n");exit(0);}
	for(usint i=1;i<=N;i++) cin>>H[i];
	for(usint i=1;i<=31;i++) bny[i]=bny[i-1]*2;
	INF=bny[31];
	for(usint i=32;i<=N;i++) bny[i]=INF+1;
	for(usint i=1;i<=N;i++) F[i]=INF;
	F[1]=0;	q.push(ichi); flag[1]=1;
}

inline void bfs()
{
	usint now,k;
	while(q.size())
	{
		now=q.front(); q.pop(); flag[now]=0;
		if(now<N && H[now+1]==H[now]+1 && F[now]+1<F[now+1])
		{
			F[now+1]=F[now]+1; 
			if(!flag[now+1]) {q.push(now+1);flag[now+1]=1;}
		}
		if(now==ichi) continue;
		for(usint i=now-1;i>=1;i--)
		{
			for(usint j=i+1;j<=N;j++)
			{
				if(H[i]+bny[now-i]<H[j]) break;
				k=F[now]+now-i+1;
				if(k>=F[j]) continue;
				F[j]=k; if(flag[j]) continue;
				q.push(j); flag[j]=1;
			}
		}
	}
}

int main()
{
	freopen("ladder.in","r",stdin);
	freopen("ladder.out","w",stdout);
	init(); bfs();
	if(F[N]==INF) cout<<-1<<endl;
	else cout<<F[N]<<endl;
	return 0;
}