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

用算术,可以一次操作钓很多次鱼

Posted by semonteer at 2006-03-07 22:46:18 on Problem 1042
In Reply To:怎么会超时了?算法是贪心。谢谢 Posted by:hdm29682 at 2006-03-07 22:35:58
> #include <iostream.h>
> #include <string.h>
> int f[25],ef[25],d[25],t[25]={0},w[25],ew[25];
> void main(){
> 	int h,n,i,j,m,mi,p,ep,lt,spsp;
> 	while((cin>>n)&&n){
> 		cin>>h;
> 		h*=12;
> 		for(i=0;i<n;++i)cin>>ef[i];
> 		for(i=0;i<n;++i)cin>>d[i];
> 		for(i=1;i<n;++i){cin>>t[i];t[i]+=t[i-1];}
> 		ep=0;spsp=0;
> 		for(j=0;j<n;++j){
> 			lt=h-t[j];
> 			memcpy(f,ef,sizeof(int)*n);
> 			memset(w,0,sizeof(int)*n);
> 			p=0;
> 			while(lt){
> 				m=mi=-1;
> 				for(i=0;i<=j;++i)
> 					if(f[i]>m){
> 						m=f[i];
> 						mi=i;
> 					}
> 					if(mi>-1){
> 						p+=f[mi];
> 						f[mi]-=d[mi];
> 						++w[mi];
> 						--lt;
> 					}
> 					else break;
> 			}
> 			if(p>ep){
> 				ep=p;spsp=t[j];
> 				memcpy(ew,w,sizeof(int)*n);
> 			}
> 		}
> 		m=spsp;
> 		for(i=1;i<n;++i){
> 			m+=ew[i];
> 		}
> 		m=h-m;
> 		cout<<(m>ew[0]?m:ew[0])*5;cout<<", ";
> 		for(i=1;i<n;++i){
> 			cout<<ew[i]*5;
> 			if(i!=n-1)cout<<", ";
> 			else cout<<" \n";
> 		}
> 		cout<<"Number of fish expected: "<<ep<<" \n\n";
> 	}
> }

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