4581634_wa.cpp

部分PKU上的源码

#include<iostream>
#include<algorithm>
using namespace std;
int H;
int N;
int T;
int fi[27];
int di[27];
int ti[27];
int fish[27];
int t[27];
int best[27];
int best_sum;
int output_number;
int getsum(int dt,int n)
{
	int mo=fi[n]-di[n]*(dt-1);
	if(mo>0) return (fi[n]+mo)*dt/2;
	else
	{
		dt=fi[n]/di[n]+1;
		mo=fi[n]-di[n]*(dt-1);
		return (fi[n]+mo)*dt/2;
	}
}
int getmax(int number)
{
	int max=0;
	fish[max]=0;
	for(int count=1;count<=number;count++)
	{
		if(fish[count]>fish[max]) max=count;
	}
	return max;
}
void getnew(int sum)
{
	best_sum=sum;
	for(int count=1;count<=N;count++) best[count]=t[count];
}
void slove()
{
	best_sum=0;
	int sum_T=T;
	for(int count=1;count<=N;count++)
	{
		int count2;
		int sum=0;
		if(count!=1) sum_T-=ti[count-1];
		for(count2=1;count2<=N;count2++) fish[count2]=fi[count2];
		memset(t,0,sizeof(t));
		for(count2=1;count2<=sum_T;count2++) 
		{
			int temp;
			temp=getmax(count);
			if(temp==0)
			{
				t[1]+=sum_T-count2+1;
				break;
			}
			if((fish[temp]-=di[temp])<0) fish[temp]=0;
			t[temp]++;
		}
		for(count2=1;count2<=count;count2++) sum+=getsum(t[count2],count2);
		if(sum>best_sum) getnew(sum);
		if(sum==best_sum)
		{
			for(count2=1;count2<=N;count2++)
			{
				if(t[count2]>best[count2]) {getnew(sum);break;}
				else if(t[count2]<best[count2]) break;
			}
		}
	}
}
void output()
{
	for(int count=1;count<=N;count++)
	{
		cout<<best[count]*5;
		if(count!=0) cout<<",";
	}
	cout<<endl;
	printf("Number of fish expected: %d",best_sum);
	output_number++;
	if(output_number!=1) cout<<endl<<endl;
}
int main()
{
	output_number=0;
	while(cin>>N)
	{
		if(N==0) return 0;
		int count;
		cin>>H;
		for(count=1;count<=N;count++) cin>>fi[count];
		for(count=1;count<=N;count++) cin>>di[count];
		for(count=1;count<=N-1;count++) cin>>ti[count];
		T=12*H;
		slove();
		output();
	}
	return 0;
}