You are given an integer array power where power[i] is the power of the ith monster.
You start with 0 mana points, and each day you increase your mana points by gain where gain initially is equal to 1.
Each day, after gaining gain mana, you can defeat a monster if your mana points are greater than or equal to the power of that monster. When you defeat a monster:
- your mana points will be reset to
0, and - the value of
gainincreases by1.
Return the minimum number of days needed to defeat all the monsters.
Example 1:
Input: power = [3,1,4] Output: 4 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 2nd monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. - Day 3: Gain 2 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster. - Day 4: Gain 3 mana points to get a total of 3 mana points. Spend all mana points to kill the 1st monster. It can be proven that 4 is the minimum number of days needed.
Example 2:
Input: power = [1,1,4] Output: 4 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster. - Day 3: Gain 3 mana points to get a total of 3 mana points. - Day 4: Gain 3 mana points to get a total of 6 mana points. Spend all mana points to kill the 3rd monster. It can be proven that 4 is the minimum number of days needed.
Example 3:
Input: power = [1,2,4,9] Output: 6 Explanation: The optimal way to beat all the monsters is to: - Day 1: Gain 1 mana point to get a total of 1 mana point. Spend all mana points to kill the 1st monster. - Day 2: Gain 2 mana points to get a total of 2 mana points. Spend all mana points to kill the 2nd monster. - Day 3: Gain 3 mana points to get a total of 3 mana points. - Day 4: Gain 3 mana points to get a total of 6 mana points. - Day 5: Gain 3 mana points to get a total of 9 mana points. Spend all mana points to kill the 4th monster. - Day 6: Gain 4 mana points to get a total of 4 mana points. Spend all mana points to kill the 3rd monster. It can be proven that 6 is the minimum number of days needed.
Constraints:
1 <= power.length <= 171 <= power[i] <= 109
class Solution:
def minimumTime(self, power: List[int]) -> int:
@cache
def dfs(mask):
cnt = mask.bit_count()
if cnt == len(power):
return 0
ans = inf
for i, v in enumerate(power):
if mask & (1 << i):
continue
ans = min(ans, dfs(mask | 1 << i) + (v + cnt) // (cnt + 1))
return ans
return dfs(0)class Solution:
def minimumTime(self, power: List[int]) -> int:
n = len(power)
dp = [inf] * (1 << n)
dp[0] = 0
for mask in range(1, 1 << n):
cnt = mask.bit_count()
for i, v in enumerate(power):
if (mask >> i) & 1:
dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + (v + cnt - 1) // cnt)
return dp[-1]class Solution {
private int n;
private long[] f;
private int[] power;
public long minimumTime(int[] power) {
n = power.length;
f = new long[1 << n];
Arrays.fill(f, -1);
this.power = power;
return dfs(0);
}
private long dfs(int mask) {
if (f[mask] != -1) {
return f[mask];
}
int cnt = Integer.bitCount(mask);
if (cnt == n) {
return 0;
}
long ans = Long.MAX_VALUE;
for (int i = 0; i < n; ++i) {
if (((mask >> i) & 1) == 1) {
continue;
}
ans = Math.min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1));
}
f[mask] = ans;
return ans;
}
}class Solution {
public long minimumTime(int[] power) {
int n = power.length;
long[] dp = new long[1 << n];
Arrays.fill(dp, Long.MAX_VALUE);
dp[0] = 0;
for (int mask = 1; mask < 1 << n; ++mask) {
int cnt = Integer.bitCount(mask);
for (int i = 0; i < n; ++i) {
if (((mask >> i) & 1) == 1) {
dp[mask] = Math.min(dp[mask], dp[mask ^ (1 << i)] + (power[i] + cnt - 1) / cnt);
}
}
}
return dp[(1 << n) - 1];
}
}using ll = long long;
class Solution {
public:
vector<ll> f;
vector<int> power;
int n;
long long minimumTime(vector<int>& power) {
n = power.size();
f.assign(1 << n, -1);
this->power = power;
return dfs(0);
}
ll dfs(int mask) {
if (f[mask] != -1) return f[mask];
int cnt = __builtin_popcount(mask);
if (cnt == n) return 0;
ll ans = LONG_MAX;
for (int i = 0; i < n; ++i) {
if ((mask >> i) & 1) continue;
ans = min(ans, dfs(mask | 1 << i) + (power[i] + cnt) / (cnt + 1));
}
f[mask] = ans;
return ans;
}
};class Solution {
public:
long long minimumTime(vector<int>& power) {
int n = power.size();
vector<long long> dp(1 << n, LONG_MAX);
dp[0] = 0;
for (int mask = 1; mask < 1 << n; ++mask) {
int cnt = __builtin_popcount(mask);
for (int i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
dp[mask] = min(dp[mask], dp[mask ^ (1 << i)] + (power[i] + cnt - 1) / cnt);
}
}
}
return dp[(1 << n) - 1];
}
};func minimumTime(power []int) int64 {
n := len(power)
f := make([]int64, 1<<n)
for i := range f {
f[i] = -1
}
var dfs func(mask int) int64
dfs = func(mask int) int64 {
if f[mask] != -1 {
return f[mask]
}
cnt := bits.OnesCount(uint(mask))
if cnt == n {
return 0
}
var ans int64 = math.MaxInt64
for i, v := range power {
if (mask >> i & 1) == 1 {
continue
}
ans = min(ans, dfs(mask|1<<i)+int64((v+cnt)/(cnt+1)))
}
f[mask] = ans
return ans
}
return dfs(0)
}
func min(a, b int64) int64 {
if a < b {
return a
}
return b
}func minimumTime(power []int) int64 {
n := len(power)
dp := make([]int64, 1<<n)
for i := range dp {
dp[i] = math.MaxInt64
}
dp[0] = 0
for mask := 1; mask < 1<<n; mask++ {
cnt := bits.OnesCount(uint(mask))
for i, v := range power {
if ((mask >> i) & 1) == 1 {
dp[mask] = min(dp[mask], dp[mask^(1<<i)]+int64((v+cnt-1)/cnt))
}
}
}
return dp[len(dp)-1]
}
func min(a, b int64) int64 {
if a < b {
return a
}
return b
}function minimumTime(power: number[]): number {
const n = power.length;
const f = new Array(1 << n).fill(-1);
function dfs(mask) {
if (f[mask] != -1) {
return f[mask];
}
const cnt = bitCount(mask);
if (cnt == n) {
return 0;
}
let ans = Infinity;
for (let i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
continue;
}
ans = Math.min(ans, dfs(mask | (1 << i)) + Math.ceil(power[i] / (cnt + 1)));
}
f[mask] = ans;
return ans;
}
return dfs(0);
}
function bitCount(x) {
let cnt = 0;
for (let i = 0; i < 32; ++i) {
if ((x >> i) & 1) {
++cnt;
}
}
return cnt;
}function minimumTime(power: number[]): number {
const n = power.length;
const dp = new Array(1 << n).fill(Infinity);
dp[0] = 0;
for (let mask = 1; mask < 1 << n; ++mask) {
const cnt = bitCount(mask);
for (let i = 0; i < n; ++i) {
if ((mask >> i) & 1) {
dp[mask] = Math.min(dp[mask], dp[mask ^ (1 << i)] + Math.ceil(power[i] / cnt));
}
}
}
return dp[dp.length - 1];
}
function bitCount(x) {
let cnt = 0;
for (let i = 0; i < 32; ++i) {
if ((x >> i) & 1) {
++cnt;
}
}
return cnt;
}