1946.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <iostream.h>
int maxs[101][101], n, e, d;
//       时间 能量
int need[101][101];
//		 路程 能量
void init()
{
	int t, s, v, h;
	cin>>n>>e>>d;

	for( t=0; t<=d; t++ )
		maxs[t][0] = 0;
	for( h=0; h<=e; h++ )
		maxs[0][h] = 0;
	for( t=1; t<=d; t++ )
	for( h=1,v=0,s=0; h<=e; h++ )
	{
		while( (v+1)*(v+1)*t <= h )
			v++;
		maxs[t][h] = v*t + (h-v*v*t)/(2*v+1);
	}
	for( h=0; h<=e; h++ )
	{
		t = 0;
		for( s=0; s<=d; s++ )
		{
			while( t<=d && maxs[t][h] < s )
				t++;
			if( t > d ) need[s][h] = -1;
			else need[s][h] = t;
		}
	}

}
int tm[21][101];
//     人  路程
int main()
{
	int i, j, k;
	init();
	for( i=0; i<=n; i++ )
	for( j=0; j<=d; j++ )
		tm[i][j] = -1;	
	tm[0][0] = 0;
	for( i=1; i<=n; i++ )
	for( j=0; j<=d; j++ )
	{
		tm[i][j] = tm[i-1][j];
		for( k=0; k<j; k++ )
			if( tm[i-1][k] >=0 && need[j-k][e-k] >=0 && ( tm[i][j]<0 || tm[i-1][k] + need[j-k][e-k] < tm[i][j] ) )
				tm[i][j] = tm[i-1][k] + need[j-k][e-k];
	}

	if( tm[n][d] < 0 ) tm[n][d] = 0;	
	cout<<tm[n][d]<<endl;
	return 0;
}