2403.杀死所有怪物的最短时间

28832:【附加题】《黑神话·悟空》，http://jsgl_liding.openjudge.cn/2024midtermtestv1/9/

https://doocs.github.io/leetcode/lc/2403/

你有一个整数数组 power，其中 power[i] 是第 i 个怪物的力量。

你从 0 点法力值开始，每天获取 gain 点法力值，最初 gain 等于 1。

每天，在获得 gain 点法力值后，如果你的法力值大于或等于怪物的力量，你就可以打败怪物。当你打败怪物时:

• 你的法力值会被重置为 0，并且
• gain 的值增加 1。

返回打败所有怪物所需的 最少 天数。

示例 1:

输入: power = [3,1,4]
输出: 4
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。
- 第 3 天: 获得 2 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。
- 第 4 天: 获得 3 点法力值，现在总共拥有 3 点法力值。 用尽所有法力值击杀第 1 个怪物。
可以证明，4 天是最少需要的天数。

示例 2:

输入: power = [1,1,4]
输出: 4
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物。
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。
- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。用尽所有法力值击杀第 3 个怪物。
可以证明，4 天是最少需要的天数。

示例 3:

输入: power = [1,2,4,9]
输出: 6
解释: 打败所有怪物的最佳方法是:
- 第 1 天: 获得 1 点法力值，现在总共拥有 1 点法力值。用尽所有法力值击杀第 1 个怪物
- 第 2 天: 获得 2 点法力值，现在总共拥有 2 点法力值。用尽所有法力值击杀第 2 个怪物。
- 第 3 天: 获得 3 点法力值，现在总共拥有 3 点法力值。
- 第 4 天: 获得 3 点法力值，现在总共拥有 6 点法力值。
- 第 5 天: 获得 3 点法力值，现在总共拥有 9 点法力值。用尽所有法力值击杀第 4 个怪物。
- 第 6 天: 获得 4 点法力值，现在总共拥有 4 点法力值。用尽所有法力值击杀第 3 个怪物。
可以证明，6 天是最少需要的天数。

提示:

• 1 <= power.length <= 17
• 1 <= power[i] <= 109

状态压缩 + 动态规划

定义 f[mask] 表示当前怪物的状态为mask 时，打败所有怪物所需的最少天数。其中 mask 是一个 n 位的二进制数，其中第 i 位为 1 表示第 i 个怪物已被击败，为 0 表示第 i 个怪物还活着。初始时 f[0]=0，其余 f[mask]=+∞。答案即为 $f[2^n-1]$。

我们在 $[1,2^n-1]$ 的范围内枚举 mask，对于每个 mask，我们枚举每个怪物 i，如果第 i 个怪物被击败，那么它可以从上一个状态 $mask\oplus 2^i$ 转移过来，转移的代价为 (power[i]+gain−1)/gain，其中 gain=mask.bitCount()。

最后，返回 $f[2^n-1]$。

时间复杂度 $O(2^n\times n)$，空间复杂度 $O(2^n)$。其中 n 为怪物的数量。

from typing import List

class Solution:
    def minimumTime(self, power: List[int]) -> int:
        n = len(power)
        max_mask = (1 << n)
        
        # dp[mask] 表示当前选择了哪些武器的最小时间
        dp = [float('inf')] * max_mask
        dp[0] = 0  # 初始状态，没有选择任何武器
        
        for mask in range(max_mask):
            selected_count = bin(mask).count('1')  # 已选择武器的数量
            gain = 1 + selected_count  # 当前增益值
            
            for i in range(n):
                if mask & (1 << i) == 0:  # 如果第 i 个武器未被选择
                    next_mask = mask | (1 << i)
                    dp[next_mask] = min(
                        dp[next_mask],
                        dp[mask] + (power[i] + gain - 1) // gain
                    )
        
        return dp[max_mask - 1]

if __name__ == '__main__':
    sol = Solution()
    pow = list(map(int, input().split()))
    print(sol.minimumTime(pow))

下面2个greedy方法，虽然能AC，但是在这个数据上会出错。

24-物院-吕金浩：发现如下数据，时间复杂度O(2^n*n)的dp做法输出68630，O(n^2)的greedy输出68631。（手在键盘上瞎划拉出的数据）。

要n<=19的话取后面19个数也行。对老师给的dp代码和我自己写的dp，邹同学、郑同学和我自己写的greedy都是这个结果

6641 41497 26416 66149 261498 716 616 5148 16416 1435 65 498 321 8682 234 54 82453 824653 465 456 8465

26416 66149 261498 716 616 5148 16416 1435 65 498 321 8682

dp 72482
greedy 72483

贪心做，这题就是要把题目里给的n个boss的力量值和1~n匹配，相除后向上取整并求和。让大的力量值尽可能去匹配大的除数，同时因为涉及到取整，可能有多个除数除出来会是一样的结果，为了避免浪费在商相同的情况下选取最小的那个除数，这样是能AC的，但是我在数学上暂时还给不出一个严格的证明。

#24 物院 郑涵予

a = list(map(int, input().split()))
n = len(a)
a.sort(reverse=True)
b = [False] * n
sum = 0
for i in range(n):
    index = -1
    time = 1e10
    for j in range(n - 1, -1, -1):
        if b[j]:
            continue
        current_time = (a[i] + j) // (j + 1)
        if time == 1e10:
            time = current_time
            index = j
        elif current_time == time:
            index = j
        else:
            break
    b[index] = True
    sum += time
print(sum)

#邹一鸣 2400011815
boss_power=sorted(list(map(int,input().split())))
pp=list(boss_power)
def findbest(l,gain):
    if len(l)==1:
        return l[0]//gain+int(bool(l[0]%gain))
    poss=[]
    for i in range(len(l)):
        if l[i]<=3*gain:
            a=l.pop(i)
            poss.append(a//gain+int(bool(a%gain))+findbest(l,gain+1))
            l.insert(i,a)
    if any(poss):
        return min(poss)
    return l[0]//gain+int(bool(l[0]%gain))+findbest(l[1:],gain+1)
a=0
for t in range(len(boss_power)):
    if boss_power[t]<=t+1:
        a+=1
        pp.remove(boss_power[t])
    else:
        a+=findbest(pp,t+1)
        break
print(a)