Codeforces Round #666 (Div. 2)E Monster Invaders 华为今年不会推出运行鸿蒙OS的手机;Deno 1.3.2发布|极客头条 异或在笔试题中的超神表现 超级码力在线编程大赛初赛 第2场 T1-T4题解 1397D. Stoned Game(博弈) Codeforces Round #666(Div.2)A~D题题解 高性能微服务架构技术选型 阿里饿了么Java4面:(数据结构+框架源码+JVM+分布式) 2020java面试总结 使用ffmpeg提取mp4内部日期重命名文件(需lua) 【剑指Offer】56.2 数组中只出现一次的数字,其他出现3次 JAVA二三事-使用IO+Properties实现动态读取文本信息 排序算法的C语言实现C代码(未更完) RT-Thread 内核学习--信号量的初步使用 【剑指Offer】57.2 和为S的连续正数序列 Qt三方库开发技术:QXlsx介绍、编译和使用 4G DTU模块的作用和功能说明 【Tips】- Wifi模块和4G无线通信 【5G核心网】 Identifiers 身份标识 DPDK支持的硬件:CPU、网卡NIC、加密引擎、基带加速器 如何根据普通ip地址获取当前地理位置 人工智能能力提升指导总结 520了,用32做个简单的小程序 程序员的数学--用贝叶斯定理来推断一个案子 文旅部新规:在线旅游网站不得擅自屏蔽删除评价 不得大数据杀熟 苏宁易购开学季消费大数据:手机以旧换新销量增长299% 做实供电服务“133” 助大数据直上“云”端 思科前程序员离职 5 月后“删虚拟机跑路”,240 万美元打水漂,网友:够狠! 抗疫代码成国博最新藏品 阿里程序员“写代码写进国博挺酷” 国博史上首次收藏代码!它们是阿里程序员写下的抗疫代码 威胜信息发布2020年上半年业绩:物联网产业进入爆发期 营收净利双增长 下月发布会不止有新品折叠屏手机 酷开的物联网家居生态野心初现 史上最全的数据库面试题 数据库面试必看 一个数据库SQL查询的数次轮回 百度智能云正式对外发布百度智能云数据库品牌GaiaDB 数据库三大泛式是什么 电力行业网管需求 IT运维管理解决方案 citrix桌面虚拟化中的运维工具Director SRE运维体系的构建和工作职责划分 运维的核心价值是什么 手游开发定制的全过程详解 开发人员透露:《赛博朋克2077》枪支泛滥 成熟的产品经理如何应对“这个需求不合理” CI/CD管道对开发和运维的重要性 APP开发的流程是怎样的 如何开发一个APP 零基础学web前端开发要学多久 如何系统学习 Web前端要学习哪些内容呢 前端工程师至少要满足四类客户的需求 前端学习计划思维导图 前端人如何选择自己的技术栈 前端人如何更快地成长
您的位置:首页 >物联网 >

Codeforces Round #666 (Div. 2)E Monster Invaders

题意:

有两种不同类型的怪物和三种不同类型的枪,

一个拥有1点生命的普通怪物。

一个拥有2点生命的老板。

这三种枪是:

手枪,对一个怪物造成1点生命伤害,时间r1

激光枪,对当前等级的所有怪物(包括老板)造成1点伤害,时间r2

AWP,立即杀死任何怪物,时间r3

这些枪最初是不装子弹的,Ziota一次只能装1把枪。

游戏的等级可以被认为是一个数组a1,a2,…,an,其中第i阶段有ai普通怪物和1个boss。由于游戏的性质,Ziota不能在杀死所有ai正常怪物之前使用手枪(第一种枪)或AWP(第三种枪)来射击boss。

如果Ziota伤害了boss但没有立即杀死它,他将被迫从当前关卡移动到任意相邻关卡i−1或者i+1,Ziota也可以随时选择移动到相邻的楼层。相邻层之间的每一次移动都由传送门管理,传送时间为d。

现在给你n个阶段,r1,r2,r3,d和每个阶段的小怪数ai,且r1<=r2<=r3

做法

很明显是一道dp题,首先我们考虑某个关卡的情况,

某关卡有两种情况:一:清完小怪并干掉boss,二:只清完小怪并且让boss血量为1

那么,我们设dp方程为dp[maxn][2],第一维表示关卡位置,第二维代表boss血量

0表示boss挂了,1表示boss还剩1滴血

那么对于某一关来说,如果上一关还未清光,我们肯定是要先返回将其扫除

因为根据贪心的想法,如果你一直留着这关的boss不干掉,最后还要原路返回,所以时间肯定不是最少的

那么这里就会有四种情况,00,01,10,11,分别表示当前状态boss血量和下一状态的boss血量

然后,如果要让boss血量为1,可以有两种选择

一种是只使用手枪,还有一种是直接使用激光枪,总时间取小即可

如果要让boss血量为0,那么选择有三种

用手枪干掉小怪+AWP,用机关枪+来回两关+手枪,用手枪+来回两关+手枪

所以这里我们要注意11这种情况,我们可以给上一关的boss留一滴血,然后到下一关也给boss留一滴血,

然后返回上一关用小手枪干掉boss,再到下一关用小手枪干掉boss

最后还要注意最后一关的情况,因为只需要清光所有阶段即可

那么有可能是在最后一关结束,也有可能是在前一关结束,需要比较一下时间,

比如倒数第二关的boss血量为1,并且你现在在最后一关

你可以让最后一关boss血量为1,然后回到前一关用小手枪关掉boss,再回到最后一关用小手枪干掉boss,

或者你直接清光最后一关,回到前一关用小手枪干掉boss,取时间最少的那个即可

code

#include<cstdio>#include<algorithm>#include<cstring>#include<map>#include<iostream>#include<vector>#include<queue>#include<string>using namespace std;typedef long long ll;const int maxn = 1e6+10;const int inf = 0x3f3f3f3f;const int mod = 1e9+7;ll n,m,k,t,mx,mi,idx,cnt,tot,sum,res,flag,st;ll a[maxn],dp[maxn][2];ll minn (ll a,ll b,ll c) {return min(a,min(b,c));}int main() {ll r1,r2,r3,d;scanf("%lld %lld %lld %lld %lld",&n,&r1,&r2,&r3,&d);for(int i=1;i<=n;i++) {scanf("%lld",&a[i]);}memset(dp,inf,sizeof dp);dp[1][0]=a[1]*r1+r3;dp[1][1]=min(a[1]*r1+r1,r2);//printf("dp[%d][%d]=%lld\ndp[%d][%d]=%lld\n",1,0,dp[1][0],1,1,dp[1][1]);for(int i=1;i<n;i++) {dp[i+1][1]=min(dp[i][0]+min(a[i+1]*r1+r1,r2),dp[i][1]+2*d+r1+min(a[i+1]*r1+r1,r2))+d;dp[i+1][0]=minn(dp[i][1]+2*d+r1+a[i+1]*r1+r3,dp[i][0]+a[i+1]*r1+r3,dp[i][1]+2*r1+2*d+min(a[i+1]*r1+r1,r2))+d;//printf("dp[%d][%d]=%lld\ndp[%d][%d]=%lld\n",i+1,1,dp[i+1][1],i+1,0,dp[i+1][0]);}printf("%lld\n",min(dp[n][0],dp[n-1][1]+2*d+r1+a[n]*r1+r3));return 0;}

郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。