洛谷P1095-守望者的逃离题解

akDiPy

Posted by 周琪岳 on July 11, 2021

本篇文章仅有题解,若要查看题目请访问

建模整理

可能的状态:

1)跑步:无代价,速度为17m/s

2)闪烁:消耗魔法值10点,1s移动60m

3)原地休息,恢复魔法值

魔法值恢复速度:4点/s,且只有处在原地休息状态才能恢复

已知魔法初值、总距离、限定时间,求行完总距离的最短时间,若无法行完,求剩下时间内能走完的最远距离

时间单位均为秒,距离单位均为米

解题思路

算法选取

对于移动+最短时间问题, 一般可以用搜索和DP实现(二分?),这一题很明显搜索不可取,只能采用动态规划。

状态

只要是动态规划,就一定有一个状态。这一题状态有两种可能,分别是设在1m、2m上,以及设在1s、2s上,由于前者的做法不好实现,所以针对后者进行思考。

dp[i]:在第i秒能行进的最远距离 (0 <= i <= T)

状态转移方程

这一题状态转移需要分类讨论,因为第i秒既可以跑步过来,也可以闪烁过来。所以两者都要处理。怎么办呢?虽然问题目前无法解决,但是无论如何总有一个贪心原则:能闪就闪,不要浪费。因为之后闪和现在闪的作用完全相同,而且后边闪万一时间过掉了,那岂不是白白浪费了机会?那闪不了的情况下,究竟是等待还是跑步呢?这就麻烦一些。我们可以DP两次:

第一次:不考虑走路的情况,能闪就闪,不能就等

第二次:综合考虑,对比 第一次的结果 以及 走路的结果 求最小值

这样应该就能解决问题了

边界

边界非常简单,第0秒肯定处在起点,故dp[0] = 0

代码实现

代码中还有一些细节,题解中就不再赘述了,为了防止p党&p+改变量名党,代码就用图片放了,建议能自己编码就自己写,下面代码仅供参考

QQ截图20210711111729.png

CSP-J2021rp++!!!