【题解-信息学奥赛一本通】1373：鱼塘钓鱼(fishing）
题目：1373：鱼塘钓鱼(fishing）
题目描述
有N个鱼塘排成一排（N<100），每个鱼塘中有一定数量的鱼，例如：N=5时，如下表：
鱼塘编号每1分钟能钓到的鱼的数量（1…1000）每1分钟能钓鱼数的减少量（1…100）当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟）
| 鱼塘编号 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 每1分钟能钓到的鱼的数量 | 10 | 14 | 20 | 16 | 9 |
| 每1分钟能钓鱼数的减少量 | 2 | 4 | 6 | 5 | 3 |
| 当前鱼塘到下一个相邻鱼塘需要的时间（单位：分钟） | 3 | 5 | 4 | 4 |
即：在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼，第2分钟内只能钓到8条鱼，……，第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟，从第2个鱼塘到第3个鱼塘需要5分钟，……
给出一个截止时间T(T<1000)，设计一个钓鱼方案，从第1个鱼塘出发，希望能钓到最多的鱼。
假设能钓到鱼的数量仅和已钓鱼的次数有关，且每次钓鱼的时间都是整数分钟。
输入
共5行，分别表示：
第1行为N；
第2行为第1分钟各个鱼塘能钓到的鱼的数量，每个数据之间用一空格隔开；
第3行为每过1分钟各个鱼塘钓鱼数的减少量，每个数据之间用一空格隔开；
第4行为当前鱼塘到下一个相邻鱼塘需要的时间；
第5行为截止时间T。
输出
一个整数（不超过231−1），表示你的方案能钓到的最多的鱼。
时空限制
1s / 64MB
样例输入
5 10 14 20 16 9 2 4 6 5 3 3 5 4 4 14样例输出
76思路（y总）
按照前后反复横跳可以将路线分为两类：
一类是经过某个点不钓鱼，接着回到这点钓鱼，后面到其他点钓，之后再回到这个点钓鱼。
另一类是从第一个点径直走到后面的点，如果不再某点钓鱼，那么之后也不会返回再钓。
由于钓鱼的数量仅与钓鱼时间有关，所以第二类路线的钓鱼数量>=第一类路线的钓鱼数量。
在第二类路线中，可以细分为n条具体的路径，分别是从1-1，从1-2，从1-2-3…，1-2-3…-n。
枚举每条具体的路径，求全局最优。
在每条路径中，假设该路径从1-2-3-…m，钓鱼时间t=总时间-路上花费的时间。要想钓鱼数量最大，肯定希望每分钟钓的鱼数量最大。
因此，问题变成了求m个序列中的前t大元素。
可以用大根堆来做。
代码
#include<bits/stdc++.h>usingnamespacestd;typedefpair<int,int>PII;constintN=100+10;intn,fish[N],sub[N],tim[N],T,ans;intwork(intm){intfishtim=T-tim[m];priority_queue<PII>heap;for(inti=1;i<=m;i++)heap.push({fish[i],i});intk=0,sum=0;while(!heap.empty()&&k<fishtim){PII t=heap.top();heap.pop();sum+=t.first;inti=t.second;if(t.first-sub[i]>0)heap.push({t.first-sub[i],i});k++;}returnsum;}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>fish[i];for(inti=1;i<=n;i++)cin>>sub[i];for(inti=2;i<=n;i++){cin>>tim[i];tim[i]+=tim[i-1];}cin>>T;for(inti=1;i<=n;i++)ans=max(ans,work(i));cout<<ans;return0;}