记录编号	47144	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]迷之阶梯	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2012-10-30 22:25:16	内存使用	95.04 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
int n,w[300],ans[300][300],answer=99999999;
int q[8000000][3]={0};
void bfs();
int main()
{
	freopen ("ladder.in","r",stdin);
	freopen ("ladder.out","w",stdout);
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		cin>>w[i];
		for (int j=0;j<=n;j++)
		{
			ans[i][j]=99999999;
		}
	}
	bfs();
	for (int i=0;i<n;i++)
	{
		if (ans[n][i]<answer)
			answer=ans[n][i];
	}
	if (answer==99999999)
		cout<<-1;
	else
		cout<<answer;
	return 0;
}

void bfs()
{
	int tou,wei;
	tou=wei=0;
	q[tou][0]=1;
	q[tou][1]=0;
	q[tou][2]=0;
	ans[1][0]=0;
	int tmp,temp;
	while (tou<=wei)
	{
		if (w[q[tou][0]]+1==w[q[tou][0]+1]&&ans[q[tou][0]+1][0]>q[tou][2]+1)
		{
			ans[q[tou][0]+1][0]=q[tou][2]+1;
			wei++;
			q[wei][0]=q[tou][0]+1;
			q[wei][1]=0;
			q[wei][2]=q[tou][2]+1;
		}
		if (q[tou][0]!=1&&ans[q[tou][0]-1][q[tou][1]+1]>q[tou][2]+1)
		{
			ans[q[tou][0]-1][q[tou][1]+1]=q[tou][2]+1;
			wei++;
			q[wei][0]=q[tou][0]-1;
			q[wei][1]=q[tou][1]+1;
			q[wei][2]=q[tou][2]+1;
		}
		if (q[tou][1]!=0)
		{
			temp=w[q[tou][0]];
			tmp=(1<<(q[tou][1]));
			for (int i=q[tou][0]+1;i<=n;i++)
			{
				if (w[i]-temp<=tmp&&ans[i][0]>q[tou][2]+1)
				{
					ans[i][0]=q[tou][2]+1;
					wei++;
					q[wei][0]=i;
					q[wei][1]=0;
					q[wei][2]=q[tou][2]+1;
				}
				if (w[i]-temp>tmp)
					break;
			}
		}
		tou++;
	}
}