跳转至

3376. 破解锁的最少时间 I

题目描述

Bob 被困在了一个地窖里，他需要破解 n 个锁才能逃出地窖，每一个锁都需要一定的 能量 才能打开。每一个锁需要的能量存放在一个数组 strength 里，其中 strength[i] 表示打开第 i 个锁需要的能量。

Bob 有一把剑，它具备以下的特征：

  • 一开始剑的能量为 0 。
  • 剑的能量增加因子 X 一开始的值为 1 。
  • 每分钟，剑的能量都会增加当前的 X 值。
  • 打开第 i 把锁，剑的能量需要到达 至少 strength[i] 。
  • 打开一把锁以后，剑的能量会变回 0 ，X 的值会增加一个给定的值 K 。

你的任务是打开所有 n 把锁并逃出地窖，请你求出需要的 最少 分钟数。

请你返回 Bob 打开所有 n 把锁需要的 最少 时间。

 

示例 1：

输入：strength = [3,4,1], K = 1

输出：4

解释：

时间 能量 X 操作 更新后的 X
0 0 1 什么也不做 1
1 1 1 打开第 3 把锁 2
2 2 2 什么也不做 2
3 4 2 打开第 2 把锁 3
4 3 3 打开第 1 把锁 3

无法用少于 4 分钟打开所有的锁，所以答案为 4 。

示例 2：

输入：strength = [2,5,4], K = 2

输出：5

解释：

时间 能量 X 操作 更新后的 X
0 0 1 什么也不做 1
1 1 1 什么也不做 1
2 2 1 打开第 1 把锁 3
3 3 3 什么也不做 3
4 6 3 打开第 2 把锁 5
5 5 5 打开第 3 把锁 7

无法用少于 5 分钟打开所有的锁，所以答案为 5 。

 

提示：

  • n == strength.length
  • 1 <= n <= 8
  • 1 <= K <= 10
  • 1 <= strength[i] <= 106

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def findMinimumTime(self, strength: List[int], K: int) -> int:
        @cache
        def dfs(i: int) -> int:
            if i == (1 << len(strength)) - 1:
                return 0
            cnt = i.bit_count()
            x = 1 + cnt * K
            ans = inf
            for j, s in enumerate(strength):
                if i >> j & 1 ^ 1:
                    ans = min(ans, dfs(i | 1 << j) + (s + x - 1) // x)
            return ans

        return dfs(0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private List<Integer> strength;
    private Integer[] f;
    private int k;
    private int n;

    public int findMinimumTime(List<Integer> strength, int K) {
        n = strength.size();
        f = new Integer[1 << n];
        k = K;
        this.strength = strength;
        return dfs(0);
    }

    private int dfs(int i) {
        if (i == (1 << n) - 1) {
            return 0;
        }
        if (f[i] != null) {
            return f[i];
        }
        int cnt = Integer.bitCount(i);
        int x = 1 + cnt * k;
        f[i] = 1 << 30;
        for (int j = 0; j < n; ++j) {
            if ((i >> j & 1) == 0) {
                f[i] = Math.min(f[i], dfs(i | 1 << j) + (strength.get(j) + x - 1) / x);
            }
        }
        return f[i];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    int findMinimumTime(vector<int>& strength, int K) {
        int n = strength.size();
        int f[1 << n];
        memset(f, -1, sizeof(f));
        int k = K;
        auto dfs = [&](this auto&& dfs, int i) -> int {
            if (i == (1 << n) - 1) {
                return 0;
            }
            if (f[i] != -1) {
                return f[i];
            }
            int cnt = __builtin_popcount(i);
            int x = 1 + k * cnt;
            f[i] = INT_MAX;
            for (int j = 0; j < n; ++j) {
                if (i >> j & 1 ^ 1) {
                    f[i] = min(f[i], dfs(i | 1 << j) + (strength[j] + x - 1) / x);
                }
            }
            return f[i];
        };
        return dfs(0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func findMinimumTime(strength []int, K int) int {
    n := len(strength)
    f := make([]int, 1<<n)
    for i := range f {
        f[i] = -1
    }
    var dfs func(int) int
    dfs = func(i int) int {
        if i == 1<<n-1 {
            return 0
        }
        if f[i] != -1 {
            return f[i]
        }
        x := 1 + K*bits.OnesCount(uint(i))
        f[i] = 1 << 30
        for j, s := range strength {
            if i>>j&1 == 0 {
                f[i] = min(f[i], dfs(i|1<<j)+(s+x-1)/x)
            }
        }
        return f[i]
    }
    return dfs(0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function findMinimumTime(strength: number[], K: number): number {
    const n = strength.length;
    const f: number[] = Array(1 << n).fill(-1);
    const dfs = (i: number): number => {
        if (i === (1 << n) - 1) {
            return 0;
        }
        if (f[i] !== -1) {
            return f[i];
        }
        f[i] = Infinity;
        const x = 1 + K * bitCount(i);
        for (let j = 0; j < n; ++j) {
            if (((i >> j) & 1) == 0) {
                f[i] = Math.min(f[i], dfs(i | (1 << j)) + Math.ceil(strength[j] / x));
            }
        }
        return f[i];
    };
    return dfs(0);
}

function bitCount(i: number): number {
    i = i - ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i + (i >>> 4)) & 0x0f0f0f0f;
    i = i + (i >>> 8);
    i = i + (i >>> 16);
    return i & 0x3f;
}

评论