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

贪心解决,放出代码,求DP之解

Posted by NARUTOACM at 2009-09-05 11:51:09 on Problem 1042
#include<iostream>
using namespace std;
int f[28],d[28],t[28];
int ff[28];
int n,h;
int time[28];
int an=INT_MIN;
int ans[28];
int sum;
int main()
{
	int i,j;
	while(scanf("%d",&n)&&n)
	{
		scanf("%d",&h);
		h=h*60;
		for(i=1;i<=n;i++)
			scanf("%d",&f[i]);
		for(i=1;i<=n;i++)
			scanf("%d",&d[i]);
		for(i=1;i<n;i++)
			scanf("%d",&t[i]);
		for(i=1;i<=n;i++)
		{
			sum=0;
			memset(time,0,sizeof(time));
			memcpy(ff,f,sizeof(int)*(i+1));
			int ji;
			h-=t[i-1]*5;
			if(h<=0)
				break;
			int hour=h;
			while(hour)
			{
				int maxf=INT_MIN;
				for(j=1;j<=i;j++)
				{
					if(ff[j]>maxf)
					{
						maxf=ff[j];
						ji=j;
					}
				}
				if(maxf<=0)
				{
					time[1]+=hour;
					break;
				}
				sum+=maxf;
				ff[ji]-=d[ji];
				if(ff[ji]<0)
					ff[ji]=0;
				time[ji]+=5;
				hour-=5;
			}
			if(sum>an)
			{
				an=sum;
				memcpy(ans,time,sizeof(int)*(n+1));
			}
		}
		cout<<ans[1];
		for(i=2;i<=n;i++)
			cout<<", "<<ans[i];
		cout<<endl;
		cout<<"Number of fish expected: "<<an<<endl<<endl;
		an=INT_MIN;
	}
	return 0;
}
另:小弟建了一个ACM群,群号89693382,希望各位加群,一起进步

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