Ming's Blog

Chicken Jockey 题解

题目分析

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

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

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

核心观察

关键点：摔落伤害只取决于位置，不取决于具体死亡的是哪个怪物。

设第 i 个位置的怪物（从 1 开始计数）需要经过的摔落次数为 i-1 次。因此： - 第 i 个位置的怪物实际受到的伤害 = 直接攻击 + 摔落伤害 = 直接攻击 + (i-1) - 第 i 个位置至少需要 h[i] - (i-1) 次直接攻击（如果结果 ≤ 0 则为 0）

动态规划

我们可以将问题转化为：如何分组使得总攻击次数最少。

假设我们把怪物分成若干组（栈）。对于第 i 个怪物： - 如果它与前一个怪物在同一组，它只需要 h[i] - 1 次直接攻击（因为会受 1 次摔落） - 如果它独立成为一个新组，它需要 h[i] 次直接攻击（没有摔落）

但是还有另一种情况：跳过某个位置，让该位置的怪物从更早的位置”继承”摔落次数。

定义 dp[i] 为处理到第 i 个位置（1-indexed）时的最少攻击次数。

转移方程：

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
)

解释： - 第一种情况：第 i 个与前一个同组，第 i 个需要 max(0, h[i] - 1) 次攻击（减 1 因为会受一次摔落） - 第二种情况：第 i 个独立成新组，那么 i-1 需要单独攻击 h[i-1] 次，第 i 个需要 max(0, h[i] - (i-1)) 次攻击（因为独立后会受 i-1 次摔落）

代码实现

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) 或 O(1)（可优化）

参考示例

对于输入 [1,2,1,3,5,2]： - 最终答案为 7