1373:鱼塘钓鱼(fishing)

2024-04-17 21:04
文章标签 fishing 钓鱼 鱼塘 1373

本文主要是介绍1373:鱼塘钓鱼(fishing),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【算法分析】

解法1:区间动规
该人只会从编号小的鱼塘走到编号大的鱼塘,不存在往回走的情况(从编号大的鱼塘走到编号小的鱼塘)。

  • 如果他仅仅往回走但不在任何鱼塘停留,那么这与不往回走钓到的鱼的数量相同,往回走是不必要的。
  • 如果存在往回走的情况,那么一定存在该人从某个第x 号鱼塘走回到第y 号鱼塘,其中y < x ,而且在第y 号鱼塘停留t y 分钟钓鱼。
  • 该情况可以由以下走法替代:先走到第y 号鱼塘,停留t y 分钟钓鱼,而后走到第x 号鱼塘。这样做还能省下往回走的时间。

1. 状态定义
集合:钓鱼方案
限制:最远走到第几个鱼塘,经过总时间
属性:钓鱼数量
条件:最大
统计量:钓鱼数量
状态定义:dp[i][j]:最远走到第i鱼塘,消耗时间j,可以钓到鱼的最大数量。
初始状态:dp[0][j]=0:在前0个鱼塘中钓鱼,消耗时间j,可以钓到鱼的最大数量为0。

2. 状态转移方程
集合:最远走到第i鱼塘,消耗时间j的钓鱼方案数。
分割集合:根据在第i个鱼塘钓鱼的时间来分割集合
记在第i鱼塘第1分钟能钓到的鱼为fish[i],第i鱼塘每分钟鱼减少量为de[i],
可以预处理出在第i鱼塘钓鱼j分钟能钓到的鱼为f[i][j]以及在第i鱼塘能钓到鱼的最大时间mxTime[i]

f[i][0] = 0;
for(int j = 1; fish[i] > 0; j++)
{
    f[i][j] = f[i][j-1] + fish[i];
    fish[i] -= de[i];
    mxTime[i] = j;
}

第i鱼塘走到第i+1鱼塘的时间为t[i],用求前缀和的方法预处理出从第1鱼塘走到第i鱼塘(只走路不钓鱼)的时间st[i]

总使用时间j,从第i-1鱼塘出发到第i鱼塘消耗时间t[i-1],那么走到第i鱼塘后,剩余可分配的时间为j-t[i-1]

  • 如果在第i鱼塘钓鱼0分钟,那么在前i-1个鱼塘消耗的时间为j-t[i-1],最大钓鱼数量dp[i][j] = dp[i-1][j-t[i-1]]
  • 如果在第i鱼塘钓鱼1分钟,那么在前i-1个鱼塘消耗的时间为j-t[i-1]-1,最大钓鱼数量dp[i][j] = dp[i-1][j-t[i-1]-1]+f[i][1]
  • 如果在第i鱼塘钓鱼2分钟,那么在前i-1个鱼塘消耗的时间为j-t[i-1]-2,最大钓鱼数量dp[i][j] = dp[i-1][j-t[i-1]-2]+f[i][2]
  • 如果在第i鱼塘钓鱼k分钟,那么在前i-1个鱼塘消耗的时间为j-t[i-1]-k,最大钓鱼数量dp[i][j] = dp[i-1][j-t[i-1]-k]+f[i][k]
  • k的最小值为0,最大时为mxTime[i],超过该时间就钓不到鱼了。同时k要满足小于等于总时间j减去从第1鱼塘一直不钓鱼走到第i鱼塘的时间st[i],即k <= j-st[i]
  • 以上所有情况取最大值

最远走到哪个鱼塘,都可能钓到最多的鱼。
记输入的总鱼塘数量为n,截止时间为endT,
最后求dp[1][endT], dp[2][endT], ..., dp[n][endT]中的最大值,就是最大钓鱼数量。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define N 105
#define T 1005
int dp[N][T];//dp[i][j]:在前i个鱼塘中钓鱼,消耗时间j,可以钓到鱼的最大数量。
int fish[N], de[N], f[N][T], t[N], st[N], mxTime[N];
int n, endT, mxFish;
int main()
{cin >> n;//n:鱼塘数量 for(int i = 1; i <= n; ++i)cin >> fish[i];//fish[i]:第1分钟第i鱼塘可以钓到的鱼的数量for(int i = 1; i <= n; ++i)cin >> de[i];//dec[i]:每过一分钟鱼可以钓到的鱼减少的数量for(int i = 1; i <= n; ++i)for(int j = 1; fish[i] > 0; ++j){f[i][j] = f[i][j-1] + fish[i];//f[i][j]:在第i鱼塘钓鱼j分钟能钓到的鱼fish[i] -= de[i];mxTime[i] = j;//mxTime[i]:在第i鱼塘能钓到鱼的最大时间(超过这一时间就钓不到鱼了) }for(int i = 1; i <= n-1; ++i){cin >> t[i];//t[i]:从第i鱼塘走到第i+1鱼塘的时间st[i+1] = st[i] + t[i];//st[i]:从第1鱼塘走到第i鱼塘的时间 }cin >> endT;//endT:截止时间 for(int i = 1; i <= n; ++i)//i:鱼塘号 for(int j = 1; j <= endT; ++j)//j:消耗时间 for(int k = 0; k <= mxTime[i] && k <= j-st[i]; ++k)//k:在第j鱼塘钓鱼k分钟 dp[i][j] = max(dp[i][j], dp[i-1][j-t[i-1]-k] + f[i][k]);for(int i = 1; i <= n; ++i)mxFish = max(mxFish, dp[i][endT]);cout << mxFish;return 0;
}

解法2:贪心
假定最远走到第i个鱼塘,由于不用走回头路,因此花费在路上的时间已经确定了。而后安排在各个鱼塘钓鱼的时间。

  • 选择当前各个鱼塘中钓鱼1分钟能钓到最多鱼的鱼塘,记录要在这个鱼塘钓鱼1分钟。
  • 在该鱼塘钓鱼1分钟后,该鱼塘下一分钟能钓到的鱼会减少。更新该鱼塘1分钟钓鱼获得的鱼的数量。
  • 而后再在当前各个鱼塘中选择钓鱼1分钟能钓到最多鱼的鱼塘,记录要在这个鱼塘钓鱼1分钟。而后更新该鱼塘每分钟钓鱼数量。
  • 重复此过程,直到所有时间都已分配。
  • 根据表格中的记录,得知在每个鱼塘的总钓鱼时间

实际执行过程为:从第1鱼塘开始向第i鱼塘走,到第x鱼塘时,在第x鱼塘钓鱼时间为记录中在第x鱼塘的总钓鱼时间,直到走到鱼塘i。
总钓鱼数量为:在执行记录的过程中,记录了的每分钟钓鱼数量的加和。
选择“能钓到最多鱼的鱼塘”的过程,可以使用优先队列来完成,使用优先队列求最值的复杂度为 O(logn)
最远走到的鱼塘从1循环到i,求出每种情况下的总钓鱼数量,比较得到最大值,即为结果。

【参考代码】

#include <bits/stdc++.h>
using namespace std;
#define N 105
int fish[N], de[N], st[N], f[N];
int n, te, endT, mxFish;
struct Cmp
{bool operator () (int a, int b){return f[b] > f[a];//鱼塘每分钟钓鱼数量更高的鱼塘更优先 }
}; 
int main()
{cin >> n;//n:鱼塘数量 for(int i = 1; i <= n; ++i)cin >> fish[i];//fish[i]:第1分钟第i鱼塘可以钓到的鱼的数量for(int i = 1; i <= n; ++i)cin >> de[i];//dec[i]:每过一分钟鱼可以钓到的鱼减少的数量for(int i = 1; i <= n-1; ++i){cin >> te;//te:从第i鱼塘走到第i+1鱼塘的时间st[i+1] = st[i] + te;//st[i]:从第1鱼塘走到第i鱼塘的时间 }cin >> endT;//endT:截止时间for(int i = 1; i <= n; ++i)//最远走到第i鱼塘{memcpy(f, fish, sizeof(fish));//将fish数组的内容复制到f数组中 priority_queue<int, vector<int>, Cmp> pq;//优先队列中保存的是鱼塘编号,每分钟钓鱼数量更高的更优先 for(int j = 1; j <= i; ++j)pq.push(j);int fishNum = 0;//可分配时间为总时间减去走到鱼塘i的时间  fishNum:钓到的鱼数量 for(int t = 1; t <= endT-st[i]; ++t){if(pq.empty())break;int mxi = pq.top();//当前每分钟钓鱼数量最大的鱼塘编号 pq.pop();fishNum += f[mxi];//总钓鱼数量增加f[mxi]f[mxi] -= de[mxi];//该鱼塘每分钟钓鱼数量减少if(f[mxi] > 0)//如果在该鱼塘还能钓鱼 pq.push(mxi); //把该鱼塘加入到优先队列 }mxFish = max(mxFish, fishNum);//更新最大钓鱼数量 }cout << mxFish;return 0;
}

这篇关于1373:鱼塘钓鱼(fishing)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/912845

相关文章

钓鱼邮件真相追踪:XDR见招拆招!

钓鱼陷阱,财富“蒸发” 如果一家规模5000人、业务遍布全球的企业之中有一位员工不小心点进了一个钓鱼邮件,会发生什么……?终端失陷?数据泄露?失去客户信任? 最让人破碎的当然是……核心资产泄露,钱没了!! 人有失手,"鱼"有逃命 某大型零售企业财务部门小张收到一封看似来自公司财务部的邮件,由于内容与其实际工作情况相符,小张打开了邮件中的附件,并点击了附件里的下载链接

如何判断网站是不是钓鱼网站?

钓鱼网站的定义 钓鱼网站是一种网络欺诈手段,通过仿冒真实网站的外观和功能,诱使用户输入个人敏感信息,如用户名、密码、信用卡详情等。这些网站通常会通过电子邮件、短信或社交媒体等方式传播,诱导用户点击链接并在看似合法的界面上输入信息。钓鱼网站的设计往往与真实网站非常相似,使得用户难以辨认真伪。 钓鱼网站的危害 钓鱼网站的危害主要包括: 个人信息泄露:用户在钓鱼网站上输入的个人信息可能会被不法分

支付时怎么辨别网络钓鱼

网络钓鱼攻击的识别与应对 网络钓鱼攻击简介 网络钓鱼攻击是一种常见的网络犯罪手段,攻击者通过伪造合法的网站、电子邮件、短信等手段,诱骗用户提供个人敏感信息,如账号密码、银行卡号等,以达到非法获取财务或个人隐私信息的目的。 如何识别网络钓鱼攻击 注意网站的URL:在访问网站时,注意查看URL是否正常。钓鱼网站通常会使用与正版网站相似但稍有不同的URL,如拼写错误、域名后缀不同等。 警惕垃

什么是鱼叉式网络钓鱼? 定义与示例

鱼叉式网络钓鱼定义 鱼叉式网络钓鱼是一种网络钓鱼攻击,通常通过恶意电子邮件针对特定个人或组织。鱼叉式网络钓鱼的目的是窃取敏感信息(例如登录凭据)或用恶意软件感染目标设备。 鱼叉式网络钓鱼者会仔细研究目标,因此攻击似乎来自目标生活中值得信赖的发件人。鱼叉式网络钓鱼电子邮件使用社交工程技术来诱使受害者点击恶意链接或附件。一旦受害者完成预期操作,攻击者就可以窃取目标合法用户的凭据并进入网络而不被发现。

【第54课】XSS跨站Cookie盗取表单劫持网络钓鱼溯源分析项目平台框架

免责声明 本文发布的工具和脚本,仅用作测试和学习研究,禁止用于商业用途,不能保证其合法性,准确性,完整性和有效性,请根据情况自行判断。 如果任何单位或个人认为该项目的脚本可能涉嫌侵犯其权利,则应及时通知并提供身份证明,所有权证明,我们将在收到认证文件后删除相关内容。 文中所涉及的技术、思路及工具等相关知识仅供安全为目的的学习使用,任何人不得将其应用于非法用途及盈利等目的,间接使用文章中的任何工具

请问不小心下载到了钓鱼软件怎么办?

🏆本文收录于《CSDN问答解惑-专业版》专栏,主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案,希望能够助你一臂之力,帮你早日登顶实现财富自由🚀;同时,欢迎大家关注&&收藏&&订阅!持续更新中,up!up!up!! 问题描述   请问不小心下载到了钓鱼软件怎么办? 下载VPN的时候不小心下载了仿冒的应用,火绒提醒有病毒后就立刻禁止下载了,文件被火绒送进了隔离区,

浅谈红队攻防之道-CobaltStrike钓鱼攻击集锦

打个比方,一片大地上,躺着一群沉睡的人,远处就是火山,马上就要爆发了,你就像个闹钟,面对这些沉睡的人,你想把他们叫醒。 你持续不断地响着,有的睡得浅的人,被你叫醒了,跟你一块去叫醒众人,但是人数太多了,你们的声音太微弱了,叫醒的人毕竟有限,而且保不齐有的人嫌烦,时不时还踢坏两个。 那么有的闹钟,怕来不及,就拿自己的生命当做原料,化成了炸弹,一下就炸醒了一大片人。 那照你这么说,炸弹比闹钟厉害多了,

钓鱼的常见几种方式

钓鱼的多种方式 office钓鱼攻击 宏与宏病毒 # 宏宏是office自带的一种高级脚本特性,通过VBA代码,可以在office中去完成某项特定的任务,而不必再重复相同的动作,目的是让用户文档中一些任务自动化# 宏病毒宏病毒是一种寄存在文档或模板的宏中的计算机病毒,打开这中文档,其中的宏就会被执行,宏病毒被激活,转移到计算机上 docx钓鱼攻击 # word远程模板执行宏利用w

如何有效防范钓鱼邮件

在当今数字化的时代,电子邮件已成为我们日常工作和生活中不可或缺的通信工具。然而,随着网络技术的不断发展,钓鱼邮件也日益猖獗,给个人和企业带来了严重的安全威胁。钓鱼邮件是一种网络欺诈手段,攻击者通过伪装成合法的机构或个人,诱骗收件人提供敏感信息,如用户名、密码、信用卡号等,或者诱导收件人点击恶意链接,下载恶意软件,从而达到窃取信息、实施诈骗或破坏系统的目的。因此,学会如何防范钓鱼邮件至关重要。

使用 GoPhish 和 DigitalOcean 进行网络钓鱼

配置环境 数字海洋VPS 我创建的丢弃物被分配了一个 IP 地址68.183.113.176 让我们登录VPS并安装邮件传递代理: ssh root@68.183.113.176apt-get install postfix 后缀配置中的点变量到我们在 DigitalOcean 中分配的 IP:mynetworks nano /etc/postfix/main.cf