poj1042贪心钓鱼

题目大意：

一个人去钓鱼 ，有n个湖排成一行，他以第一个湖为起点，从一个湖到下一个湖需要 时间t[i]。第i个湖的鱼一开始每单位时间（以5分钟为单位）能钓上的鱼为f[i],每掉5分钟，则每个单位时间能掉上的鱼减少d[i]。求能掉上的最大的鱼的数目。以及在每个湖所呆的时间（可能有多个情况，要求的是尽量在一个湖呆长一点时间的情况）。

解题思路：假如我们走路不需要时间的话，那么这道题就变的简单了，直接用贪心策略，哪个湖现在每单位时间能钓的鱼数目最多，则在哪个湖钓。 

我们假设只在前i个湖钓鱼，那么我们走路的时间是不是可以求出来了。那么求出这个时间以后，用总时间减去走路时间就得到了能用与钓鱼的时间，在减去走路时间后，我们就可以在前i个湖之间直接“瞬移”（这个词也是在写完后看别人的解题报告中学到的，感觉很好理解），既然可以瞬移的话，我们每次选择现在单位时间能钓的最多的鱼的湖，在这个湖钓一个单位时间，鱼总数增加，这个湖单位时间能掉的鱼减少，然后我们再次 选择单位时间可以钓最多的湖，。。。（循环）。。。。。

 

可以结合着代码看。

 

 

#include<iostream>
using namespace std;
#define len 110
int main()
{
	int n,h;//n表示湖的个数,h表示时间
	int f[len],d[len],t[len];//fi是每个湖的初始值，di是每5分钟减少的值，ti是从 湖i到湖i+1所用的时间
	int i,j;
	int tot[len];
	int wait[len][len];//wait[i][j]表示第i个枚举中在第j个湖呆的时间
	while(true)
	{
	scanf("%d",&n);
	if(n==0)break;
	scanf("%d",&h);
	for(i=0;i<n;i++)
		scanf("%d",&f[i]);
	for(i=0;i<n;i++)
		scanf("%d",&d[i]);
	for(i=0;i<n-1;i++)
		scanf("%d",&t[i]);
	memset(tot,0,sizeof(tot));
	for(i=0;i<n;i++)
	memset(wait[i],0,sizeof(wait[i]));
	for(i=0;i<n;i++)//枚举只到前i个湖钓鱼
	{
		
		int tl=0;//从第0个湖走到第i个湖，走路所用总时间
		for(j=0;j<i;j++)
			tl+=t[j];
		int td=h*12-tl;//能用于钓鱼的时间=总时间-走路时间
		int a[len];
		for(j=0;j<=i;j++)//得到临时初始鱼欲望数组
		{
			
			a[j]=f[j];
		}
		
		for(;td>0;td--)//在时间用完之前
		{
			int max=0;
			int index=0;
			for(int k=0;k<=i;k++)//选一个最大下标
			{
				if(max<a[k])
				{
					max=a[k];
					index=k;
					
				}
			}
			wait[i][index]++;
			if(a[index]>=0)
			{
				
				tot[i]+=a[index];//在最大的这里掉一个单位时间的鱼
			}
			if(a[index]>=0)
				a[index]-=d[index];//钓鱼处减少
		}
	}
	int maxt=-99;
	int mindex=0;
	for(i=0;i<n;i++)
	{
		if(maxt<tot[i])
		{
			maxt=tot[i];
			mindex=i;
		}
	}
	for(i=0;i<n;i++)
	{
		cout<<wait[mindex][i]*5;
		if(i!=n-1)
		cout<<", ";
		else
			cout<<endl;
	}
	cout<<"Number of fish expected: "<<maxt<<endl;
	cout<<endl;
	}
	
	return 0;
}