T29886: 黑神话·悟空

状态压缩dp, http://cs101.openjudge.cn/practice/29886/

T9:【附加题】《黑神话·悟空》

状态dp, http://jsgl_liding.openjudge.cn/2024midtermtestv1/9/

在以小说《西游记》为背景设定的《黑神话·悟空》游戏中，你将扮演一位“天命人”，为了探寻昔日传说的真相，踏上一条充满危险与惊奇的西游之路。

现在你来到了盘丝洞，你需要战胜这里的所有 boss，boss 的力量是参差不齐的，只有当你的法力值大于等于 boss 的力量才能战胜它。boss 的力量用整数数组 power 表示，其中 power[i] 是第 i 个 boss 的力量。

虽然扮演的是“天命人”，但也需要从零开始，你的初始法力值为 0。在这里，你只有通过做任务——打小蜘蛛才能获得法力值的提升，每做完一个任务你可以获得 gain 点法力值，初始 gain 值为 1。

你打败 boss 后它会恼羞成怒，吞掉你所有的法力值，换句话说，你的法力值将被清零，但同时你会得到一个名叫金花玉萼的道具，使用后可以使 gain 值增加 1，之后你做一次任务将可以获得更多的法力值。

显然，你可以先拼命做任务直到可以一次性打败所有 boss，但你讨厌蜘蛛并想速速通关，希望做最少的任务就可以打败所有 boss。

因此你的目标是：以最少的任务量打败盘丝洞里所有的 boss。请根据怪物力量 power 数组计算打败所有 boss 所需要的最少任务量。

输入

一个整数数组 power，数字用空格隔开，第 i 个数字表示第 i 个 boss 的力量

输出

一个数字，表示打败所有 boss 所需要的最少任务量

样例输入

输入1:
3 1 4

输入2:
1 1 4

输入3:
1 2 4 9

样例输出

输出1:
4
解释1: 打败所有 boss 的最佳方法是:
- 做第 1 次任务: gain 值为 1，获得 1 点法力值（总共 1 点），击杀第 2 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 2 次任务: gain 值为 2，获得 2 点法力值（总共 2 点）。
- 做第 3 次任务: gain 值为 2，获得 2 点法力值（总共 4 点），击杀第 3 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 4 次任务: gain 值为 3，获得 3 点法力值（总共 3 点），击杀第 1 个 boss。
至此，需要做 4 次任务才能最快击杀全部 boss。可以证明，4 次是最少需要的任务量。

输出2:
4
解释2: 打败所有 boss 的最佳方法是:
- 做第 1 次任务: gain 值为 1，获得 1 点法力值（总共 1 点），击杀第 1 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 2 次任务: gain 值为 2，获得 2 点法力值（总共 2 点），击杀第 2 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 3 次任务: gain 值为 3，获得 3 点法力值（总共 3 点）。
- 做第 4 次任务: gain 值为 3，获得 3 点法力值（总共 6 点），击杀第 3 个 boss。
可以证明，4 次是最少需要的任务量。

输出3:
6
解释3: 打败所有 boss 的最佳方法是:
- 做第 1 次任务: gain 值为 1，获得 1 点法力值（总共 1 点），击杀第 1 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 2 次任务: gain 值为 2，获得 2 点法力值（总共 2 点），击杀第 2 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 3 次任务: gain 值为 3，获得 3 点法力值（总共 3 点）。
- 做第 4 次任务: gain 值为 3，获得 3 点法力值（总共 6 点）。
- 做第 5 次任务: gain 值为 3，获得 3 点法力值（总共 9 点），击杀第 4 个 boss，击杀之后法力值清零，gain 值加 1。
- 做第 6 次任务：gain 值为 4，获得 4 点法力值（总共 4 点），击杀第 3 个 boss。
可以证明，6 次是最少需要的任务量。

提示

1 <= power.length <= 19 1 <= power[i] <= 10^9 你需要考虑较优的时间、空间复杂度

来源

leetcode 2403，题解 https://doocs.github.io/leetcode/lc/2403。本题数据有加强，递归方法会被卡。

这个问题本质上是 动态规划 / 状压 DP，来源是 LeetCode 2403（Minimum Time to Kill All Monsters），只不过这里的背景换成了《黑神话·悟空》。

问题抽象

有 n 个 boss，每个 boss 有力量 power[i]。
初始 gain = 1，每次做任务能获得 gain 点法力值。
击杀一个 boss 需要攒到 ≥ power[i] 点法力值。
击杀后：
- 法力值清零
- gain += 1
目标：最少任务次数。

关键思路

顺序无关，但顺序影响代价 因为 gain 会逐步增加，所以顺序选择很重要。打小 boss 先，可以更快提升 gain，从而更快打大 boss。
状态压缩 DP
- 用一个 bitmask 表示已经打掉了哪些 boss。
- 状态：dp[mask] = 打掉 mask 中所有 boss 所需的最少任务数
- 转移：从当前状态 mask，尝试击杀一个未击杀的 boss j：
  - 当前 gain = popcount(mask) + 1（已经杀了多少个 boss，gain 就是多少+1）。
  - 要杀 power[j]，需要做 ceil(power[j] / gain) 次任务。
  - 于是：
```
dp[mask | (1<<j)] = min(dp[mask | (1<<j)], dp[mask] + ceil(power[j]/gain))
```
复杂度
- 状态数 2^n，转移时最多 n 次，复杂度 O(n * 2^n)。
- n ≤ 19，所以大约 19 * 2^19 ≈ 1e7，可行。

Python 实现

python

from math import ceil
from functools import lru_cache

def min_tasks(power):
    n = len(power)
    INF = 10**18
    dp = [INF] * (1 << n)
    dp[0] = 0

    for mask in range(1 << n):
        # 已经击杀的 boss 数量
        killed = bin(mask).count("1")
        gain = killed + 1
        for j in range(n):
            if not (mask >> j) & 1:
                need = (power[j] + gain - 1) // gain  # 等价于 ceil(power[j]/gain)
                nxt = mask | (1 << j)
                dp[nxt] = min(dp[nxt], dp[mask] + need)
    
    return dp[(1 << n) - 1]

if __name__ == "__main__":
    import sys
    power = list(map(int, sys.stdin.read().split()))
    print(min_tasks(power))

T29886: 黑神话·悟空 ​

T29886: 黑神话·悟空