poj1042题解

注意：虽然看起来这样做是在各个湖之中切换来切换去，但是实际上不管我们1慧1慧选择的湖的顺序是怎么样的，我们都可以对应成在第i个湖钓鱼pi慧时间，是并没有违反题目的钓鱼规则。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<iostream>
using namespace std;
const int max_hui=400;
const int maxn=25;
int n,hui;
int t[maxn+2],f[maxn+2],d[maxn+2],ans_list[maxn+2],st[maxn+2],ans;
int tf[maxn+2],tans_list[maxn+2],tans;

void work(int hui,int n)
{
	int x;
	ans=0;
	memset(ans_list,0,sizeof(ans_list));
	for (int h=1;h<=hui;++h) {
		x=0;
		for (int i=1;i<n;++i)
			if (f[x]<f[i])
				x=i;
		ans_list[x]++;
		ans+=f[x];
		if (f[x]>d[x])
			f[x]-=d[x];
		else
			f[x]=0;
	}
}

bool is_better(int n)
{
	int i;
	if (ans>tans) return true;
	if (ans<tans) return false;
	for (i=0;i<n-1;++i)
		if (ans_list[i]!=tans_list[i])
			break;
	return ans_list[i]>tans_list[i];
}

int main()
{
	void init();
	void backup();
	bool first=true;
	while (1) {
		if (first)
			first=false;
		else
			printf("\n");
		init();
		if (!n) break;
		tans=-1;
		memcpy(tf,f,sizeof(f));//backup
		for (int end=0;end<n;++end) {
			work(hui-st[end],end+1);
			if (is_better(end+1)) {
				tans=ans;
				memcpy(tans_list,ans_list,sizeof(ans_list));
			}
			memcpy(f,tf,sizeof(f));//restore
		}
		for (int i=0;i<n-1;++i)
			printf("%d, ",tans_list[i]*5);
		printf("%d \n",tans_list[n-1]*5);
		printf("Number of fish expected: %d \n",tans);
	}
	return 0;
}

void init()
{
	scanf("%d",&n);
	if (n==0) return;
	scanf("%d",&hui);hui*=12;
	for (int i=0;i<n;++i)
		scanf("%d",f+i);
	for (int i=0;i<n;++i)
		scanf("%d",d+i);
	st[0]=0;
	for (int i=0;i<n-1;++i) {
		scanf("%d",t+i);
		st[i+1]=st[i]+t[i];
	}
}