尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
【题解-信息学奥赛一本通】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;}结果
RELATED

相关推荐

聊天机器人、AI助手、AI智能体到底有什么区别?搞懂这层才算真正入门

聊天机器人、AI助手、AI智能体到底有什么区别?搞懂这层才算真正入门

聊天机器人、AI助手、AI智能体到底有什么区别?搞懂这层才算真正入门基于规则或简单模型的问答系统,主要用于FAQ检索和客服首轮分流,比如“怎么退货”“营业时间”这类高频标准问题。遇到超出预设范围的问题,它只能说“这个我不太清…

📅 2026/11/18 2:46:21
7.Java 深度练习

7.Java 深度练习

Java程序的基本结构记住这个模板,以后每个Java文件都长这样:public class‌:声明一个公共类,public表示这个类可以被其他任何类访问;class是定义类的关键字。HelloWorld‌:这是类名。根据 Java 规范&#x…

📅 2026/10/4 19:10:47
Seed-VC模型选择实战:从入门到精通的完整指南

Seed-VC模型选择实战:从入门到精通的完整指南

Seed-VC模型选择实战:从入门到精通的完整指南 【免费下载链接】seed-vc zero-shot voice conversion & singing voice conversion, with real-time support 项目地址: https://gitcode.com/GitHub_Trending/se/seed-vc Seed-VC是一个强大的零样本语音转换…

📅 2026/9/22 23:51:56
MORE NEWS

更多资讯

📰

工地太忙根本没时间复习考试?考电工证在考消防证,电子证书怎么拿?

工地太忙根本没时间复习考试?考电工证在考消防证,电子证书怎么拿? 工地太忙根本没时间复习考试,考电工证在考消防证的你是不是也这样?手里活儿干不完,脑袋里却总想着考个证,怕以后干不动了。但现在考证的门槛越来越高,尤其是 电子证书…

📰

石城考电工证多少钱千万别踩坑 电工证过期了怎么复审延期

石城考电工证多少钱千万别踩坑 电工证过期了怎么复审延期 证书过期了不知道怎么复审延期,这事儿真的不能拖,不然不仅影响工作,还可能被单位追责。最近很多电工朋友都遇到这个问题,特别是石城地区的, 千万别踩坑…

📰

奉贤区哪里报考电工证 郑州报考避坑指南:怕考不过白交培训费?先看这篇

奉贤区哪里报考电工证 郑州报考避坑指南:怕考不过白交培训费?先看这篇 怕考不过白交培训费?你不是一个人。最近几年,随着国家对安全生产的重视,电工证等特种作业操作证的门槛越来越高,很多人在选择培训机构时踩了坑,花了几千块报名,结果考试没过,还…

📰

奉贤区哪里报考电工证?含金量高的电工证怎么考最靠谱?

奉贤区哪里报考电工证?含金量高的电工证怎么考最靠谱? 工地太忙根本没时间复习考试,尤其是像许昌刚来上海打工的小李这种,每天从早干到晚,连吃饭时间都紧张,更别提抽空去复习电工证的理论知识了。但你知道吗?电工证的含金量可是越来越高,尤其是在建筑…

📰

河北电工证办理费用2024年最新解读,网上查询教你避坑

河北电工证办理费用2024年最新解读,网上查询教你避坑 不知道去哪报名怕被中介坑?你不是一个人。河北电工证办理费用一直是特种作业人员最关心的问题之一,特别是现在网上信息五花八门,真假难辨,很多想考证的人都在犹豫:到底多少钱?在哪办?有没有坑…

📰

漯河办电工证到哪里在哪考,工地太忙根本没时间复习考试怎么办

漯河办电工证到哪里在哪考,工地太忙根本没时间复习考试怎么办 工地太忙根本没时间复习考试,这几乎是每个准备考电工证的工友最真实的写照。特别是在漯河这样的城市,建筑项目密集,工期紧,工人们每天在工地上奔波,根本顾不上系统复习。但问题是,…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬