【题解-信息学奥赛一本通】1373：鱼塘钓鱼(fishing）

题目1373鱼塘钓鱼(fishing题目描述有N个鱼塘排成一排N100每个鱼塘中有一定数量的鱼例如N5时如下表鱼塘编号每1分钟能钓到的鱼的数量1…1000每1分钟能钓鱼数的减少量1…100当前鱼塘到下一个相邻鱼塘需要的时间单位分钟鱼塘编号12345每1分钟能钓到的鱼的数量101420169每1分钟能钓鱼数的减少量24653当前鱼塘到下一个相邻鱼塘需要的时间单位分钟3544即在第1个鱼塘中钓鱼第1分钟内可钓到10条鱼第2分钟内只能钓到8条鱼……第5分钟以后再也钓不到鱼了。从第1个鱼塘到第2个鱼塘需要3分钟从第2个鱼塘到第3个鱼塘需要5分钟……给出一个截止时间T(T1000)设计一个钓鱼方案从第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大元素。可以用大根堆来做。代码#includebits/stdc.husingnamespacestd;typedefpairint,intPII;constintN10010;intn,fish[N],sub[N],tim[N],T,ans;intwork(intm){intfishtimT-tim[m];priority_queuePIIheap;for(inti1;im;i)heap.push({fish[i],i});intk0,sum0;while(!heap.empty()kfishtim){PII theap.top();heap.pop();sumt.first;intit.second;if(t.first-sub[i]0)heap.push({t.first-sub[i],i});k;}returnsum;}intmain(){cinn;for(inti1;in;i)cinfish[i];for(inti1;in;i)cinsub[i];for(inti2;in;i){cintim[i];tim[i]tim[i-1];}cinT;for(inti1;in;i)ansmax(ans,work(i));coutans;return0;}结果