Minimum Time to Break Locks I
medium · 32.2% accepted · 104 likes · top 10%
array · dynamic programming · backtracking · bit manipulation · depth-first search · bitmask
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 ith 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 ith 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.
Solution