Gone Fishing
题目描述
John 要去钓鱼。他有h 小时的时间（1 ≤ h ≤ 16），并且该区域有n 个湖泊（2 ≤ n ≤ 25），这些湖泊通过一条单向道路依次连接。
John 从第 1 个湖出发，但可以在任意一个湖结束。
他只能从湖 i 前往湖 i+1，但可以选择是否在某个湖停留。
对于每个 i = 1,…,n-1，从湖 i 到湖 i+1 需要ti 个 5 分钟单位（0 < ti ≤ 192）。
- 例如：t3 = 4 表示从湖 3 到湖 4 需要 20 分钟。
为了规划行程，John 收集了以下信息：
对每个湖 i：
- 初始 5 分钟内预计能钓到的鱼数为fi（fi ≥ 0）
- 每经过一个 5 分钟，下一时间段的鱼数会减少di（di ≥ 0）
规则说明：
- 如果某一时间段预计能钓的鱼数 ≤ di，那么下一时间段该湖将不再有鱼。
- 每个湖的钓鱼时间必须是5 分钟的整数倍。
- 假设没有其他人影响鱼的数量。
你的任务是：帮助 John 规划每个湖停留的时间，使得总钓鱼数量最大。
输入格式
包含多组测试数据：
- 每组第一行是整数 n（湖的数量）
- 第二行是整数 h（可用时间，单位：小时）
- 第三行是 n 个整数：fi（每个湖初始鱼数）
- 第四行是 n 个整数：di（每个湖递减量）
- 第五行是 n-1 个整数：ti（湖之间的移动时间，单位为 5 分钟）
当 n = 0 时，输入结束。
输出格式
对于每组数据：
输出一行：每个湖停留的时间（单位：分钟），用逗号分隔
再输出一行：
Number of fish expected: 最大鱼数不同测试用例之间输出一个空行
注意（重要）
如果存在多个最优方案：
- 优先选择在湖 1 停留时间更长的方案
- 若仍相同，再比较湖 2，依此类推
即：按字典序优先最大化前面的湖停留时间
示例输入
2 1 10 1 2 5 2 4 4 10 15 20 17 0 3 4 3 1 2 3 4 4 10 15 50 30 0 3 4 3 1 2 3 0示例输出
45, 5 Number of fish expected: 31 240, 0, 0, 0 Number of fish expected: 480 115, 10, 50, 35 Number of fish expected: 724题目分析
很好，你这个总结已经接近“标准题解表达”了，我帮你稍微润色 + 补一个具体例子，让它变成考试满分级别的答案。
完整思路
我们的钓鱼次数是有限的，每 5 分钟可以进行一次决策。
为了让总收益最大化，在每一次钓鱼时，都应该选择当前能获得鱼最多的湖。
由于每个湖的鱼量会随着时间递减，因此这是一个动态最优选择问题，可以使用：
⭐优先队列（大根堆）维护当前每个湖的收益
但本题还有一个重要限制：
❗ 只能从 1 号湖往后走，不能随意选择湖
因此我们必须：
🔹 外层策略：枚举终点 k
我们枚举：
最多可以走到哪个湖（1 ~ k）因为走到更远的湖需要时间，如果时间不够就不能到达。
🔹 内层策略：贪心分配时间
在固定的 1 ~ k 范围内：
- 每 5 分钟做一次决策
- 从当前所有湖中选鱼最多的湖
- 钓鱼后该湖鱼量减少，再放回堆
🔹 最终策略
在所有 k 的方案中，选择：
✔ 总收益最大的方案
✔ 若相同，按题目要求字典序优先
代码：
#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);boolfirst=true;while(true){intn;cin>>n;if(!cin||n==0)break;inth;cin>>h;vector<int>f(n),d(n),t(n);for(inti=0;i<n;i++)cin>>f[i];for(inti=0;i<n;i++)cin>>d[i];for(inti=0;i<n-1;i++)cin>>t[i];intT=h*12;// 转换成5分钟单位vector<int>best_time(n,0);intbest_fish=-1;for(intk=0;k<n;k++){inttravel=0;for(inti=0;i<k;i++)travel+=t[i];intremain=T-travel;if(remain<=0)continue;vector<int>cur_f=f;vector<int>time(n,0);// 大根堆：鱼多优先，编号小优先（关键）priority_queue<pair<int,int>>pq;for(inti=0;i<=k;i++){pq.push({cur_f[i],-i});// 用 -i 保证编号小优先}inttotal=0;for(inti=0;i<remain;i++){auto[fish,neg_id]=pq.top();pq.pop();intid=-neg_id;total+=fish;time[id]++;cur_f[id]=max(0,cur_f[id]-d[id]);pq.push({cur_f[id],-id});}// 更新最优解if(total>best_fish){best_fish=total;best_time=time;}elseif(total==best_fish){if(time>best_time){best_time=time;}}}// 输出if(!first)cout<<"\n";first=false;for(inti=0;i<n;i++){if(i)cout<<", ";cout<<best_time[i]*5;}cout<<"\n";cout<<"Number of fish expected: "<<best_fish<<"\n";}return0;}
