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

#define M 201
#include <climits>
#include <fstream>
using namespace std;
int main()
{
	int i,j,k,n,h[M]={0},f[M]={0};//{}中为0时,编译器会将数组全初始化为0,否则只初始化f[0]
	unsigned int power[32]={1};//2^1~2^31
	ifstream fin("ladder.in");
	ofstream fout("ladder.out");
	fin>>n;
	for(i=1;i<=n;i++)	fin>>h[i];
	for(i=1;i<=31;i++)power[i]=power[i-1]<<1;//计算2^i
	for(i=2;i<=n;i++)
	{//阶段i:从第一阶到达第i阶; 状态f[i]:到达第i阶所需的最少移动步数
		f[i]=INT_MAX;
		for(j=1;j<=i-1;j++)//到达第i阶有两种情况:(1)从第j(j<i)阶退至k(k<j)阶跳至i阶
			for(k=1;k<=j;k++)//(2)从i-1阶直接到达i阶(h[i]==h[i-1]+1)
				if(h[i]-h[k]<=power[j-k]&&f[j]+j-k+1>0&&f[i]>f[j]+j-k+1)f[i]=f[j]+j-k+1;
			//其中当k==j==i-1时,相当于h[i]-h[i-1]<=1(2^0),即从i-1阶直接到i阶的情况
	}
	if(f[n]!=INT_MAX)
		fout<<f[n]<<endl;
	else
		fout<<-1<<endl;
	fin.close();fout.close();
	return 0;
}