Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

wa大侠帮助下!

Posted by yogafrank at 2008-08-12 16:01:08 on Problem 1042
#include <iostream>
#include <cstring>
#include <fstream>
#define in cin
using namespace std;

int h, n, f[26], d[26], t[25], best[26], current[26], bestnum, currentnum;
/*
将C前面路上的开销减去
*/
void roadtimecost ( int c )
{
	for ( int i = 1; i < c; i ++ )
		h -= 5 * t[i];
}
/*
C前面还有地方有鱼
*/
bool fishavailable ( int c )
{
	bool flag = false;

	for ( int i = 1; i <= c; i ++ )
		if ( f[i] > current[i] * d[i] )
			flag = true;

	return flag;
}

void solve ( int i )
{
	int j;

	roadtimecost ( i );
   
	while ( h > 0 && fishavailable ( i ) )
	{
		int max = -1, index = -1;
                /*贪心选择一个可以获得最多鱼的*/
		for ( j = 1; j <= i; j ++ )
			if ( f[j] - current[j] * d[j] > max )
			{
				index = j;
				max = f[j] - current[j] * d[j];
			}

		h -= 5;
		current[index]++;
	}

        /*算出当前策略可以得到的鱼*/
	for ( j = 1; j <= i; j ++ )
	{
		int temp = f[j];

		for ( int k = 0; k < current[j]; k ++ )
		{
			if ( f[j] >= d[j] )
			{
				currentnum += f[j];
				f[j] -= d[j];
			}
			else
				currentnum += f[j];
		}

		f[j] = temp;
	}
}

int main ()
{
	ifstream in ( "1042.txt" );
    int i, left;
	bool flag = false;

	while ( in >> n )
	{
		if ( n == 0 )
			break;

		in >> h;
		h *= 60;

		for ( i = 1; i <= n; i ++ )
			in >> f[i];
		for ( i = 1; i <= n; i ++ )
			in >> d[i];
		for ( i = 1; i < n; i ++ )
			in >> t[i];

		bestnum = 0;
		for ( i = 1; i <= n; i ++ )
		{
			int th = h;
			left = h;
            currentnum = 0;
			memset ( current, 0, sizeof ( current ) );
			solve ( i );

			if ( currentnum > bestnum )
			{
				memcpy ( best, current, sizeof ( current ) );
				bestnum = currentnum;
				
				for ( int k = 1; k < i; k ++ )
					left -= t[k] * 5;
			}
			h = th;
		}

		if ( flag )
			cout << endl;

		for ( i = 1; i <= n; i ++ )
			left -= best[i] * 5;
                /*收获的鱼为0,那么将时间全部花在1那边*/
		if ( bestnum == 0 )
		{
			for ( i = 1; i <= n; i ++ )
				best[i] = 0;
			left = h;
		}

		cout << best[1] * 5 + left;

		for ( i = 2; i <= n; i ++ )
			cout << ", " << best[i] * 5;
		cout << endl;
		cout << "Number of fish expected: " << bestnum << endl;
		flag = true;
	}

	return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator