消滅怪物

相似題目：46. 全排列

思路

題目要求一個技能施放順序，能把怪物打死。
因為技能的最大數量很少，所以能把所有的排列方式都嘗試過一遍。
嘗試的過程當中，根據怪物血量跟閾值的關係，去更新牠的血量。

程式碼

#include <iostream>
#include <vector>
#include <array>
#include <climits>
using namespace std;
const int MX = 11;
array<int, MX> damage, threshold;
// n 技能總數量
// i 當前來到的技能編號
// m 怪物剩下的血量
int solve(int n, int i, int m) {
    if(m <= 0) {
        return i; //之前施放了 i 個技能後，怪物就死了
    }
    if(i == n) { // 技能用完，怪獸尚未死亡
        return INT_MAX; 
    }
    int res = INT_MAX;
    for(int j = i; j < n; ++j) {
        swap(damage[i], damage[j]);
        swap(threshold[i], threshold[j]);
        res = min(solve(n, i + 1, m - (m <= threshold[i] ? 2 * damage[i] : damage[i])), res); // 如果血量低於閾值，受到雙倍傷害
        swap(damage[i], damage[j]);
        swap(threshold[i], threshold[j]);
    }
    return res;
}
int main() {
    int t, n, m;
    cin >> t;
    while(t--) {
        cin >> n >> m;
        for(int i = 0; i < n; ++i) {
            cin >> damage[i];
            cin >> threshold[i];
        }
        int res = solve(n, 0, m);
        cout << (res == INT_MAX ? -1 : res) << endl;
    }
}

複雜度分析

• 時間複雜度：$O(n!)$
• 空間複雜度：$O(n)$