题解 | #消灭怪物#

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

int f(std::vector<std::vector<int>> &nums, std::vector<bool> &used, int blood)
{
    // num 已经使用的技能数， blood 剩余血量
    if (blood <= 0) {
        return 0;
    }  

    int min_num = INT_MAX;
    for (int i = 0; i < nums.size(); i++) {
        if (used[i]) {continue;} // 技能已经使用了

        used[i] = true;
        int hurt;
        if (blood <= nums[i][1]) {
            hurt = nums[i][0]*2;
        } else {
            hurt = nums[i][0];
        }
        int val = f(nums, used, blood - hurt);
        min_num = std::min(min_num, val);
        used[i] = false;
    }
    return min_num == INT_MAX? INT_MAX : min_num + 1;
}

int main() {
    int T;
    std::cin >> T;
    int m;  // 血量
    int n;  // 技能数
    int A;  // 技能伤害
    int x;  // 低于x血量， 技能伤害翻倍
    while (T--) {
        std::cin >> n >> m;
        std::vector<std::vector<int>> nums(n, std::vector<int>(2, 0));
        std::vector<bool> used(n, false);   // 技能点是否使用了
        for (int i = 0; i < n; i++) {
            std::cin >> A >> x;
            nums[i][0] = A;
            nums[i][1] = x;
        }
        int res = f(nums, used, m);
        if (res == INT_MAX) {res = -1;}
        std::cout << res << std::endl;
    }
}
// 64 位输出请用 printf("%lld")

n < 10 说明支持时间复杂度 n!的算法， 直接递归