梵梵最近在玩 PVZ 泳池关卡,不考虑僵尸的移动以及植物的冷却时间,他想知道只运用樱桃炸弹(消耗阳光 150,樱桃炸弹可以消灭以它为中心周围 9 个格子内的僵尸)和荷叶(消耗阳光 25),在假设僵尸可以一次被樱桃炸弹消灭的情况下,消灭所有僵尸的最少阳光消耗量。
时间: 2024-04-03 10:35:22 浏览: 167
很抱歉,我的前面的回答有误。由于我是一个语言模型,无法保留对话的上下文。下面是新的回答:
针对这个问题,我们可以使用动态规划来解决。我们定义状态 $f(i,s)$ 表示前 $i$ 行的僵尸已经被消灭,目前已经使用的阳光数为 $s$ 的情况下,消灭所有僵尸的最小阳光消耗量。其中 $0\leq i\leq 9$,$0\leq s\leq 1500$。我们需要求解的答案即为 $f(9,0)$。
对于状态 $f(i,s)$,我们考虑当前行使用樱桃炸弹和不使用樱桃炸弹两种情况:
- 如果当前行使用樱桃炸弹,那么我们需要枚举樱桃炸弹的放置位置 $j$,然后计算使用樱桃炸弹后消灭当前行及其上下两行的所有僵尸所需要的阳光数 $c$。此时,对于前 $i-1$ 行的状态,我们可以递归调用 $f(i-1,s-c)$ 来计算。具体来说,我们可以将前 $i-1$ 行的状态转移至 $f(i-1,s-c)$,并在 $f(i-1,s-c)$ 的基础上加上消耗 $c$ 的阳光数。状态转移方程为:
$$
f(i,s) = \min_{j=1}^5 \Big\{ f(i-1,s-c_j)+150 \Big\}
$$
- 如果当前行不使用樱桃炸弹,那么我们需要计算使用荷叶清除当前行僵尸所需要的阳光数 $c$,并将前 $i-1$ 行的状态转移至 $f(i-1,s-c)$,在 $f(i-1,s-c)$ 的基础上加上消耗 $c$ 的阳光数。状态转移方程为:
$$
f(i,s) = f(i-1,s-c)+25
$$
由于状态 $f(i,s)$ 只依赖于 $f(i-1,\cdot)$,因此可以使用滚动数组将状态空间优化至 $O(S)$,其中 $S$ 表示状态总数。最终的时间复杂度为 $O(N^2S)$,空间复杂度为 $O(S)$。
下面是具体的 Python 代码实现:
阅读全文