Ming's Blog

Chicken Jockey 题解

题目描述

有 n 个怪物叠在一起，怪物 i (从下到上编号) 初始血量为 h[i]。

一次攻击可以对任意一个怪物造成 1 点伤害。当怪物血量 ≤ 0 时死亡，其上方的所有怪物会掉落。掉落的怪物中，底部的怪物会受到等于其下方怪物数量的摔落伤害。如果摔落后死亡，过程继续。

求最少需要多少次攻击才能消灭所有怪物。

---

解法

问题类型：线性 DP（状态转移只与前几个状态相关，呈线性关系）

核心观察：摔落伤害只取决于位置，不取决于具体死亡的是哪个怪物。

定义：dp[i] 为处理到第 i 个位置（从 0 开始）时的最少攻击次数

初始条件：dp[0] = h[0]（第 1 个怪物需要 h[0] 次攻击）

状态转移： - 与前一个怪物同组：dp[i] = dp[i-1] + max(0, h[i] - 1) - 独立成新组：dp[i] = dp[i-2] + h[i-1] + max(0, h[i] - i)

dp[i] = min (dp[i − 1] + max (0, h[i] − 1), dp[i − 2] + h[i − 1] + max (0, h[i] − i))

解释： - 情况 1（与前一个同组）：第 i 个怪物会受 1 次摔落伤害，所以需要 max(0, h[i] - 1) 次直接攻击 - 情况 2（独立成新组）：第 i-1 个怪物需要单独攻击 h[i-1] 次，第 i 个怪物会受到 i 次摔落伤害，所以需要 max(0, h[i] - i) 次直接攻击

代码实现

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    dp = [0] * n
    dp[0] = a[0]

    for i in range(n - 1):
        # 情况 1: 与前一个同组
        dp[i + 1] = dp[i] + a[i + 1] - 1

        # 情况 2: 独立成新组
        if i > 0:
            val = max(0, a[i + 1] - i - 1)
            dp[i + 1] = min(dp[i + 1], dp[i - 1] + a[i] + val)

    print(dp[n - 1])

t = int(input())
while t > 0:
    solve()
    t -= 1

时间复杂度：O(n) 空间复杂度：O(n)