class Solution {
public:
long long minimumTime(vector<int>& power) {
}
};
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 <= 171 <= power[i] <= 109原站题解
python3 解法, 执行用时: 3096 ms, 内存消耗: 104.4 MB, 提交时间: 2023-10-21 19:59:40
class Solution:
def minimumTime(self, power: List[int]) -> int:
n = len(power)
@cache
def dfs(mask):
cnt = mask.bit_count()
if cnt == n:
return 0
ans = inf
for i in range(n):
cur = 1 << i
if mask & cur:
continue
ans = min(ans, dfs(mask | cur) + ceil(power[i] / (cnt + 1)))
return ans
return dfs(0)
cpp 解法, 执行用时: 148 ms, 内存消耗: 16.5 MB, 提交时间: 2023-10-21 19:59:20
class Solution {
public:
long long minimumTime(vector<int>& power) {
int n = power.size();
vector<long long> dp(1 << n, 1e18);
dp[0] = 0LL;
for (int mask = 0; mask < (1 << n); mask++) {
int gain = __builtin_popcount(mask) + 1;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
continue;
}
dp[mask | (1 << i)] = min(dp[mask | (1 << i)], dp[mask] + (long long)ceil((double)power[i] / gain));
}
}
return dp.back();
}
};
java 解法, 执行用时: 106 ms, 内存消耗: 42.4 MB, 提交时间: 2023-10-21 19:58:53
class Solution {
public long minimumTime(int[] power) {
// 状态压缩动态规划。
int n = power.length;
int mask = 1 << n;
// 定义动态规划数组，dp[mask] 表示打编码为 mask 的怪兽需要的时间。
long[] dp = new long[mask];
Arrays.fill(dp, Long.MAX_VALUE);
// 不打怪不需要时间。
dp[0] = 0L;
// 枚举所有的编码情况。
for (int i = 0; i < mask; i++) {
// 枚举一个编码中的 1，通过 i - (1 << j) 来状态转移。
for (int j = 0; j < n; j++) {
if ((i & (1 << j)) != 0) {
// 每一次打怪以后法力值都会归零，而打怪结束以后的增长速度就是状态编码中 1 的
// 个数加上 1（也就是编码 i 的 1 的个数），可以直接计算出需要等待的时间。
// bits 代表 i - (1 << j) 的 1 的个数，也是此时的法力值增长速度。
int bits = Integer.bitCount(i);
// 需要的时间是 dp[i ^ (1 << j)] + power[j] / bits(向上取整)。保留最小时间。
dp[i] = Math.min(dp[i ^ (1 << j)] + (power[j] + bits - 1) / bits, dp[i]);
}
}
}
// 击败所有怪的时间就是答案。
return dp[mask - 1];
}
}
python3 解法, 执行用时: 2484 ms, 内存消耗: 31.6 MB, 提交时间: 2023-10-21 19:58:35
class Solution:
def minimumTime(self, power: List[int]) -> int:
dp = [{} for j in range(len(power)+1)]
dp[0][0]=0 #边界条件
for cur in range(1,len(power)+1): #遍历打怪数量
for j,choose in enumerate(power): # 遍历当前选择的怪物
for ls in dp[cur-1]: #遍历上一层的所有状态
s = ls|(1<<j)
if s==ls: #这说明当前这只怪物打过了，跳过
continue
dps = dp[cur-1][ls]+(choose-1)//cur+1 # 注意当前怪物需要天数不能直接用整除，但可以直接调math.ceil
if s not in dp[cur] or dp[cur][s]>dps: # s首次出现或者找到一个更优值时更新
dp[cur][s]=dps
return dp[-1][(1<<(len(power)))-1]
golang 解法, 执行用时: 408 ms, 内存消耗: 21.3 MB, 提交时间: 2023-10-21 19:58:17
func bitCount(n int) int {
cnt := 0
for n > 0 {
cnt++
n &= n - 1
}
return cnt
}
func minimumTime(power []int) int64 {
n := len(power)
var dp func(mask int) int64
cache := map[int]int64{0:0}
dp = func(mask int) int64 {
if ans, ok := cache[mask]; ok {
return ans
}
bits := bitCount(mask)
var ans int64 = 17000000000
for i := 0; i < n; i++ {
if (1<<i)&mask > 0 {
temp := dp(mask ^ (1 << i))
temp += int64(power[i] / bits)
if power[i]%bits != 0 {
temp++
}
if temp < ans {
ans = temp
}
}
}
cache[mask] = ans
return ans
}
return dp((1 << n) - 1)
}