本篇文章仅有题解,若要查看题目请访问
建模整理
可能的状态:
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+改变量名党,代码就用图片放了,建议能自己编码就自己写,下面代码仅供参考
CSP-J2021rp++!!!