记录编号	74248	评测结果	AAAAAAAAAA
题目名称	[NOIP 2010冲刺十三]迷之阶梯	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.013 s
提交时间	2013-10-24 17:02:05	内存使用	0.32 MiB

#include<fstream>
#include<cmath>
using namespace std;

ifstream fi("ladder.in");
ofstream fo("ladder.out");

const int MAXN = 201 , K = 7 ;
int N , h [ MAXN ] , f[ MAXN ], mul[ 32 ];

int main()
{
	int i , j , k ;
	mul[0] = 1 ;
	for ( i = 1 ; i <= 31 ; i ++ ) mul[ i ] = mul[ i - 1 ] << 1 ;
	fi >> N ;
	for ( i = 1 ; i <= N ; i ++ ) fi >> h[i] ;
	for ( i = 1 ; i <= N ; i ++ ) f[i] = 100000 ;
	f[1] = 0 ;
	for ( i = 2 ; i <= N ; i++ )
	{

		if ( h[ i ] == h[ i - 1 ] + 1 )
			f[ i ] = min ( f[ i ] , f[ i - 1 ] + 1 ) ;

		for ( j = 1 ; (j <= 31 && i - j >= 1 ) ; j++ )
			for ( k = i + 1 ; k <= N ; k++ )
				if ( h[ k ] <= h[ i - j ] + mul[ j ] )//你可以跳到高度不超过当前阶梯高度+ 2^k的任何一步阶梯
					f[ k ] = min ( f[ k ] , f[ i ] + j + 1 );

	}

	if ( f[ N ] >= 100000 ) fo << "-1" << endl ;
	else fo << f[ N ] << endl ;
	
	return 0 ;
}