3376. Minimum Time to Break Locks I

3376. Minimum Time to Break Locks I

Description

Bob is stuck in a dungeon and must break n locks, each requiring some amount of energy to break. The required energy for each lock is stored in an array called strength where strength[i] indicates the energy needed to break the i^th lock.

To break a lock, Bob uses a sword with the following characteristics:

• The initial energy of the sword is 0.
• The initial factor X by which the energy of the sword increases is 1.
• Every minute, the energy of the sword increases by the current factor X.
• To break the i^th lock, the energy of the sword must reach at least strength[i].
• After breaking a lock, the energy of the sword resets to 0, and the factor X increases by a given value K.

Your task is to determine the minimum time in minutes required for Bob to break all n locks and escape the dungeon.

Return the minimum time required for Bob to break all n locks.

Example 1:

Input: strength = [3,4,1], K = 1

Output: 4

Explanation:

Time	Energy	X	Action	Updated X
0	0	1	Nothing	1
1	1	1	Break 3^rd Lock	2
2	2	2	Nothing	2
3	4	2	Break 2^nd Lock	3
4	3	3	Break 1^st Lock	3

The locks cannot be broken in less than 4 minutes; thus, the answer is 4.

Example 2:

Input: strength = [2,5,4], K = 2

Output: 5

Explanation:

Time	Energy	X	Action	Updated X
0	0	1	Nothing	1
1	1	1	Nothing	1
2	2	1	Break 1^st Lock	3
3	3	3	Nothing	3
4	6	3	Break 2^n^d Lock	5
5	5	5	Break 3^r^d Lock	7

The locks cannot be broken in less than 5 minutes; thus, the answer is 5.

Constraints:

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

Hints/Notes

• 2024/12/09
• state compression dp
• 0x3F’s solution(checked)
• Biweekly Contest 145

Solution

Language: C++

class Solution {
public:
    vector<int> dp;
    int k, n;

    int findMinimumTime(vector<int>& strength, int K) {
        n = strength.size();
        k = K;
        dp.resize(1 << n, -1);
        int res = dfs(0, strength);
        return res;
    }

    int dfs(int mask, vector<int>& strength) {
        if (mask == ((1 << (strength.size())) - 1)) {
            return 0;
        }
        if (dp[mask] != -1) {
            return dp[mask];
        }
        int X = __builtin_popcount(mask) * k + 1;
        int res = INT_MAX;
        for (int i = 0; i < n; i++) {
            if (((mask >> (n - 1 - i)) & 1) == 0) {
                int t = (strength[i] + X - 1) / X;
                res = min(res, dfs(mask | 1 << (n - 1 - i), strength) + t);
            }
        }
        dp[mask] = res;
        return res;
    }
};