1042.txt

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

//////////////////////////////////////////////////
//Gone Fishing
//
//

#include <stdio.h>
#define time alsfl

int n, h, f[30], d[30], t[30];

int ans[30],best_get;


bool init()
{
	int i;
	
	scanf( "%d", &n );
	if( n <= 0 ) return false;
	
	scanf( "%d", &h );
	h *= 12;

	for( i=0; i<n; i++ ) scanf( "%d", &f[i] );
	for( i=0; i<n; i++ ) scanf( "%d", &d[i] );
	for( i=0; i<n-1; i++ ) scanf( "%d", &t[i] );
	
	best_get = -1;
	for( i=0; i<n; i++ ) ans[i] = 0;

	return true;
}

int main()
{
	int k, lake, fish_time, end, tm, total_get,cas=0;
	int can_get[30],fish_times[30];

	while( init() )
	{
		fish_time = h;
		for( end = 0; end < n && fish_time >= 0 ; end++ )
		{		
			for( lake = 0; lake <= end; lake++ )
				fish_times[lake] = 0 , can_get[lake] = f[lake];

			total_get = 0;			

			for( tm = fish_time; tm ; tm-- )
			{

				for( k = -1,lake = 0; lake <= end; lake++ )
					if( k < 0 || can_get[lake] > can_get[k] ) 
						k = lake;

				fish_times[k]++;
				total_get += can_get[k];

				can_get[k] -= d[k];
				if( can_get[k] < 0 ) can_get[k] = 0;
			}
		
			if( total_get > best_get )
			{
				best_get = total_get;
				for( lake = 0; lake <= end ; lake++ )
					ans[lake] = fish_times[lake];
			} 
			
			fish_time -= t[end];
		}

		for( lake = 0; lake < n ; lake++ )
		{
			if( lake ) printf( ", " );
			printf( "%d", ans[lake]*5 );
		}
		printf( "\n" );

		printf( "Number of fish expected: %d\n\n", best_get);

	}
	
	return 0;
}