菲洛嘉青春动能素135HA FILLMED® NCTF 135HA LED指示灯的常见故障分析 智微智能 Elkhartlake K075终端,零售产业新选择 天空蓝拓客管理系统详细介绍版 muso公链项目 天使计划 是什么?[秘] 独家揭秘最前沿的家装“黑科技”——掌赋 天博体育欧洲杯特辑,东道主法兰西的失意2016 亚马逊的送货侦察员 学习听起来像挡泥板 Google Comics Factory使ML变得容易 笑着说-男性或女性 Amazon Rekognition中更好的人脸检测 关于Spaun的真相-大脑模拟 两个聊天机器人彼此聊天-有趣又怪异 GANPaint:将AI用于艺术 WCF和WF给予社区 从耳朵到脸 所有神经网络的深层缺陷 蠕虫在尾巴上平衡杆子 Kickstarter上的OpenCV AI套件 TensorFlow-Google的开源AI和计算引擎 众包取代新闻工作者 Google的DeepMind学会玩街机游戏 哑机器人V智能机器人 .NET与.NET 5融为一体 Google的深度学习-语音识别 LInQer将.NET LINQ移植到Javascript 机器人TED演讲-新的图灵测试? GAN的发明者加入苹果 您的智能手机会监视您键入的内容 人工智能帮助改善国际象棋 Zalando Flair NLP库已更新 TensorFlow 1.5包含移动版本 AlphaGo输了一场比赛-比分3-1 虚拟机器学习峰会 Microsoft开源AI调试工具 SharePoint走向移动 F#4.0发出文化变革的信号 克里斯蒂拍卖AI艺术品 人工智能如何区分 Facebook在蒙特利尔的新AI实验室 Mozilla想要您的声音 微软使用极深的神经网络赢得ImageNet 建立AI合作伙伴关系 .NET Core 3-Microsoft几乎回到了起点 神经网络-更好的销售商? Google使用AI查找您的住所 虹膜-适用于Android的Siri证明苹果没有优势 TensorFlow 2提供更快的模型训练 深度学习研究人员将为Google工作
您的位置:首页 >物联网 >

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;}

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