题解 | #消灭怪物#

#include <iostream>
#include<vector>
#include<string>
using namespace std;
#include <string>
#define INT_MAX 2147483647
vector<vector<int>> powers(11, vector<int>(2));
bool used[11] = { 0 };
int ans = INT_MAX;
void func(vector<vector<int>>& powers, int size, int Hp, int time) {
    //递归的终止条件
    if (Hp <= 0) {
        if (time < ans) {
            ans = time;
        }
        return;
    }
    for (int i = 0; i < size; i++) {
        //选择技能，发现技能选过了就跳过
        if (used[i] == 1) {
            continue;
        }
        //到达斩杀，双倍伤害
        if (Hp <= powers[i][1]) {
            used[i] = 1;
            func(powers, size, Hp - (2 * powers[i][0]), time + 1);
            used[i] = 0;
        }
        //没有到达斩杀线，就1倍伤害
        else {
            used[i] = 1;
            func(powers, size, Hp - powers[i][0], time + 1);
            used[i] = 0;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int chances = 0;
    cin >> chances; // 第一行为n组测试数据
    while (chances--) {
        int size, Hp;  // size 为技能数目，hp为怪物血量
        cin >> size >> Hp;
        int  i = 0;
        int temp = size;
        while (temp--) {
            int harm, blood;  // harm 为单倍伤害， blood 为双倍伤害的血量下限
            cin >> harm >> blood;
            powers[i][0] = harm;
            powers[i][1] = blood;
            i++;
        }
        func(powers, size, Hp, 0);
        if (ans == INT_MAX)
            ans = -1;
        cout << ans << '\n';
        //将ans重新设置
        ans = INT_MAX;
    }
}

思路：从记录最少数量time，从选1，选2，选3 这个递归搜索，终止条件为怪物血量将为0或者小于等于 0，期间如果怪兽血量满足我选择的技能的双倍伤害的条件就双倍伤害，然后递归，最后发现如果time大于我的answer就记录，同时需要注意的是，每次选择技能要有一个used数组去标记当前这个技能是不是已经用了,如果发现answer任然是INT_MAX则返回-1