本题中约翰进行钓鱼旅行，有一定的可用时间 $h$，有 $n$ 个湖，从湖 $1$ 出发，可在任意湖结束。从一个湖到下一个湖需要一定时间 $t_i$，每个湖有初始预计钓鱼数 $f_i$ 以及钓鱼数减少速率 $d_i$。目标是规划旅行以最大化钓到的鱼的数量，且在每个湖花费的时间为 $5$ 的倍数，同时在存在多种方案时，优先在湖 $1$ 停留更长时间，若仍有平局，依次考虑在湖 $2$ 等停留更长时间。

算法标签

• 动态规划（Dynamic Programming）：由于需要在不同的湖之间分配时间，并且每个湖的钓鱼情况随时间变化，动态规划可以记录不同时间分配和湖之间移动情况下的最大钓鱼数，通过状态转移方程来逐步计算出最优解。
• 贪心算法（Greedy Algorithm）：在每个决策点（即在每个湖停留的时间），可以考虑贪心的策略，例如优先选择当前钓鱼数较多且减少速率相对较小的湖进行钓鱼，但由于最终结果可能受到整体时间和湖之间移动时间的影响，贪心算法可能不能直接得到最优解，不过可以作为一种辅助思路来分析问题。
• 枚举法（Enumeration）：因为湖的数量 $n$ 和可用时间 $h$ 都有一定的范围，所以可以通过枚举在每个湖停留的时间（以 $5$ 分钟为单位）来尝试所有可能的时间分配方案，然后找出能钓到最多鱼的方案。

解题思路

1. 预处理数据：读取输入的 $n$、$h$、$f_i$、$d_i$ 和 $t_i$，将时间 $h$ 转换为 $5$ 分钟的间隔数 $total\_intervals$。
2. 动态规划 / 枚举：
   • 定义一个数组或矩阵（例如 $dp$）来记录在不同湖和不同时间间隔下的最大钓鱼数。
   • 枚举在每个湖的停留时间（以 $5$ 分钟为单位），对于每个湖 $i$ 和时间间隔 $j$，计算在该湖停留 $j$ 个 $5$ 分钟间隔时的钓鱼数，并更新 $dp$ 数组。
   • 在计算钓鱼数时，考虑鱼数的减少速率 $d_i$，如果当前钓鱼数小于等于 $d_i$，则该湖后续无鱼可钓。
   • 同时，考虑湖之间的移动时间 $t_i$，确保总时间不超过可用时间 $total\_intervals$。
3. 处理多种方案的优先级：在找到最大钓鱼数的方案后，检查是否存在多种方案。如果存在，按照在湖 $1$ 停留时间尽可能长，若仍有平局则依次考虑在湖 $2$ 等停留时间更长的规则，选择符合要求的方案。
4. 输出结果：输出在每个湖停留的时间（以 $5$ 为单位），以及最大钓鱼数。

代码实现步骤（c++）

#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <vector>
using namespace std;
double eps=0.0000001;
struct node
{
	int val,id;
	node(){}
	node(int a,int b)
	{val=a;id=b;}
};
node tm[100005];
int cmp(node a,node b)
{
	if (a.val!=b.val)
		return a.val>b.val;
	else
		return a.id<b.id;
}
 
int f[30],d[30],t[30];
int sum_t[30];
int sum[30];
int ans_num[30]; 
int tmp_num[30];
int min(int a,int b){return a<b?a:b;}
int main()
{ 
	int i,j,k,n,h;
	int maxx;
	int cnt=1;
 
	while(cin>>n&&n)
	{
		maxx=-1;
		cin>>h;
		h*=12;
		for (i=1;i<=n;i++)
			scanf("%d",&f[i]);
		for (i=1;i<=n;i++)
			scanf("%d",&d[i]);
		for (i=1;i<=n-1;i++)
		{
			scanf("%d",&t[i]);
			sum_t[i]=sum_t[i-1]+t[i];		//移动耗时前缀和
		}
		
		int end;
		
		for (end=1;end<=n;end++)
		{
			int ok=0;
			int res_time=h-sum_t[end-1];  //除掉移动花费的时间，剩下的为可以钓鱼的时间
			
			for (i=1;i<=end;i++)	//把每一次耗时可能掉的鱼数都放到tm数组
			{
				int tmp=f[i];
				while(tmp>0)
				{
					tm[++ok].val=tmp;
					tm[ok].id=i;
					if (d[i]==0)  //当作能钓n次
					{
						for (j=1;j<=h;j++)
						{
							tm[++ok].val=tmp;
							tm[ok].id=i;
						}
						break;
					}
					tmp-=d[i];	
				}
			}
			sort(tm+1,tm+1+ok,cmp);	//降序排序
			int len=min(ok,res_time);	
			int ans=0;
			memset(tmp_num,0,sizeof(tmp_num));
			for (i=1;i<=len;i++)	
			{	
				ans+=tm[i].val;
				
					tmp_num[tm[i].id]++; 
			}
			if (ans>=maxx)		//大于等于都可能更新
			{
				if (res_time>ok)		//如果钓完了鱼还有剩余时间,就把时间全部浪费在第一个鱼塘
				{
				tmp_num[1]+=res_time-ok;	
				}
				int flag=0;
				if (ans==maxx)
				{
					for (i=1;i<=n;i++)		//按找题目要求,鱼数一样取在序号小的鱼塘花费时间较多的答案
					{
					if (tmp_num[i]==ans_num[i]) continue;
					if (tmp_num[i]<ans_num[i]) {flag=1;break;}
					if (tmp_num[i]>ans_num[i]) {flag=0;break;}
					}
				}
				if (flag) continue;
				maxx=ans;
				memset(ans_num,0,sizeof(ans_num));
				for (i=1;i<=n;i++)
					ans_num[i]=tmp_num[i]; 
		 	
			}
		 
		
		}
		
		 if (cnt!=1)printf("\n");
	    cnt++;
		for (i=1;i<=n;i++)
		{
			if (i!=1)		 printf(", ");
			printf("%d",5*ans_num[i]);
		}
		printf("\nNumber of fish expected: %d\n",maxx);
	
 	
	}
 
	return 0;
	
}