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

唔虾米TLE啊。。。贪心应该不慢啊。。。

Posted by alafeizai at 2012-04-06 18:05:47 on Problem 1042
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

using namespace std;
const int MAXT=30;
int f[MAXT],d[MAXT],t[MAXT];
int lakeget[MAXT];
int tmp[MAXT];
//int ans[MAXT];
int counts[MAXT];
int ct[MAXT];
//int ans[MAXT];

int main()
{
	int n,h;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			break;
		/*
		memset(f,0,sizeof(f));
		memset(d,0,sizeof(d));
		memset(t,0,sizeof(t));
		*/
		memset(counts,0,sizeof(counts));
		scanf("%d",&h);
		h*=12;

		int totalfish=0;

		for(int i=0;i<n;i++)
		{
			scanf("%d",&f[i]);
		}
		
		for(int i=0;i<n;i++)
		{
			scanf("%d",&d[i]);
		}

		for(int i=1;i<n;i++)
		{
			scanf("%d",&t[i]);
		}

		counts[0]=h;		

		for(int i=0;i<n;i++)
		{
			int times = h;
			memset(lakeget,0,sizeof(lakeget));
			memset(ct,0,sizeof(ct));
			for(int j=0;j<=i;j++)
			{
				times-=t[j];
				tmp[j]=f[j];
			}

			while(times-->0)
			{
				int index=0,nmaxf=tmp[0];
				for(int j=0;j<=i;j++)
				{
					if(tmp[j]>nmaxf)
					{
						nmaxf=tmp[j];
						index=j;
					}
				}

				lakeget[index]+=tmp[index];
				tmp[index]-=d[index];
				ct[index]=ct[index]+1;
				if(tmp[index]<0)
				{
					tmp[index]=0;
				}
			}
			int fishnow=0;
			for(int j=0;j<=i;j++)
                        {
                                fishnow+=lakeget[j];
                        }

			if(fishnow > totalfish)
			{
				totalfish = fishnow;
				//memset(ans,0,sizeof(ans));
				//memset(counts,0,sizeof(counts ));
				memcpy(counts,ct,sizeof(ct));

				/*
				for(int j=0;j<=i;j++)
				{
					//ans[j]=lakeget[j];
					counts[j]=ct[j];
				}
				*/
			} 
		}

		printf("%d",counts[0]*5);
		for(int i=1;i<n;i++)
                        printf(", %d",counts[i]*5);
		printf("\nNumber of fish expected: %d\n\n",totalfish);

	}
	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