POJ 1042 钓鱼问题 贪心枚举及动态规划

题意描述：

john现有h个小时的空闲时间，他打算去钓鱼。john钓鱼的地方共有n个湖，所有的湖沿着一条单向路顺序排列（john每在一个湖钓完鱼后，他只能走到下一个湖继续钓）， john必须从1号湖开始钓起，但是他可以在任何一个湖结束他此次钓鱼的行程。john在每个湖中每5分钟钓的鱼数（此题中以5分钟作为单位时间），随时间的增长而线性递减。而每个湖中头5分钟可以钓到的鱼数以及每个湖中相邻5分钟钓鱼数的减少量，input中均会给出。并且John从任意一个湖走到它下一个湖的时间input中也都给出。

问题：

求一种方案，使得john在有限的h小时中可以钓到尽可能多的鱼。

output中需包括john在所有湖边所呆的时间，以及最后总的钓鱼数。

算法分析：

由于每个湖都必须经过，且只经过一次，所以john花在路中的总时间是确定的。

在这个条件下，可以想成john学会了“瞬间移动”，即：他可以在任何时间，移动到任何他想去的湖，而移动的过程无需时间。

于是，john只需在每个5分钟的开始“瞬间移动”到当前5分钟中能钓到最多的鱼的湖中，且只钓5分钟的鱼。

这样可以保证john钓到尽可能多的鱼。

只要枚举john的行程是从第一个湖到第k个湖（1<=k<=n）,比较出最大的钓鱼数，就是题目所求的最佳方案。

贪心算法：

每次选择一个局部最优策略进行实施，而不去考虑对今后的影响。

实质是枚举加贪心算法的应用，两种算法混用在校赛里面作为压轴题，这个要小心

#include <iostream>
#include <cstring>
#define MAXN 26
using namespace std;
int t[MAXN]={0},f[MAXN],F[MAXN],d[MAXN],ans[MAXN],ANS[MAXN];
//ans为枚举过程中记录每个湖应该停留时间，ANS为最优的结果
int main(){
	int h,n,i,time,max,j,sum,p,k;
	while (cin>>n,n)
	{
		cin>>h;
		h = h*12;
		for (i = 0;i < n;i++) cin>>F[i];
		for (i = 0;i < n;i++) cin>>d[i];
		for (i = 1;i < n;i++)
		{
			cin>>time;
			t[i] = time + t[i-1];//统计走到某个湖的时间
		}
		memset(ANS,0,sizeof(ANS));
		for (max = 0 , i = 1;i <= n;i++)//枚举，max记录最多鱼的数目
		{
			memset(ans,0,sizeof(ans));
			for (j = 0; j < i;j++)
			{
				f[j] = F[j];
			}
			for (j = 0,sum = 0;j < h - t[i-1];j++)//减去在湖之间所走的时间，相当于瞬间转移
			{
				for (p = 0,k = 1;k < i;k++)
				{
					if (f[k] > f[p])
					{
						p = k; //p标记初始状态下鱼最多的水池
					}
				}
				if (f[p] <= 0)
				{
					ans[0]+=h-t[i-1]-j;
					break;
				}
				sum+=f[p];//计算钓到鱼的总数
				f[p]-=d[p];//水池里面鱼减少后的数目
				ans[p]++;//对应池塘钓鱼时间+1
			}
			if (sum > max)
			{
				max = sum;
				memcpy(ANS,ans,sizeof(ans));
			}
			if (sum == max)
			{
				for (j = 0;j < i;j++)
				{
					if (ans[j] != ANS[j])
					{
						break;
					}
				}
				if (ans[j] > ANS[j])
				{
					memcpy(ANS,ans,sizeof(ans));
				}
			}
		}
		for (i = 0;i < n-1;i++)
		{
			cout<<ANS[i]*5<<", ";
		}
		cout<<ANS[n-1]*5<<endl;
		cout<<"Number of fish expected: "<<max<<endl<<endl;	
	}
	return 0;	
}