stdKonjac's Blog

 要做到不可替代,就要与众不同。

【魔棒】

有一个英雄,初始生命值是 hp(生命值无上限),在接下来的 n 秒内,每秒会受到一次伤害,第 i 秒受到的伤害值为 a[i]。

这个英雄有一个道具“魔杖”,魔杖的初始能量为 0 ,每受到一次伤害,积攒一点能量。在英雄受到伤害后,可以立即释放魔棒中的能量,回复 15*[能量点数] 的生命值,且魔棒的点数清零。释放能量有施法间隔 cd(cd是正整数),即相邻的两次释放的时间间隔至少有 cd 秒。任何时刻当 hp<=0 时视为死亡。

问这个英雄存活下来的前提下,cd 的值最大可以是多少?注意,若 a[i] 为负,受到“伤害”后实际上生命值是增加的,魔棒仍然积攒能量。

输入格式

第一行两个正整数 n,hp ,含义如题目所述。
第二行 n 个整数,分别是 a[1]..a[n]。

输出格式

输出一个数,即最大的 cd ,cd 是一个正整数。
如果 cd 没有上限,输出 “No upper bound.”;如果无论如何都不能存活,输出 -1。

样例数据 1

输入

8 30
20 5 30 4 10 5 20 20

输出

2

备注

【数据范围】
对于 30% 的数据,n≤12
对于 100% 的数据,n≤500, |a[i]| ≤1000

首先看到这道题容易想到二分CD的值再去验证,问题就在于到底怎么去验证,正解是转化为一个蛋疼的图论问题,预处理出一直不用魔法直到i时刻用魔法后的血量,然后枚举每个时刻算出这个时刻能到哪个时刻,i能到j时刻就建一条边,最后dfs一遍即可,注意dfs时判断两点间的距离>=CD的理由是为了确保能跑下一步后再跑,若<CD,要么跑下一步就死了,要么这个状态已经是前面某个状态能跑的极限转移过的了。但是当从起点出发或者只需再跑一步就到终点不需要考虑下一步的情况也能够转移。

下面是代码:

 

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.