islands打炉石传说

一。题目

islands最近在玩一款游戏“炉石传说”，又名“魔兽英雄传”。炉石传说是一款卡牌类对战的游戏。游戏是两人对战，总的来说里面的卡牌分成两类，一类是法术类，另一类是随从牌（所谓随从就是怪物）。

为了简化问题，现在假设随从牌的作用是召唤一个具有一定攻击力的怪物，法术牌的作用是给某个随从增加一定攻击力。随从牌和法术牌的使用都需要消耗一定的法力值。现在islands有10点法力值，手上有n张牌（islands最多有10张牌，否则他会被爆牌T_T），有些是法术牌，有些是随从牌。islands现在是大劣势，他想要利用这10点法力值使得召唤出来的所有随从的攻击力总和最高（法力值可以不用完）。注意，任何法术牌都必须使用在某个召唤出来的随从上，也就是如果islands没有召唤过随从，他将不能使用任何法术牌。告诉islands他能召唤的随从的总攻击力最大是多少。

【输入格式】

每组数据首先输入一个n(0<=n<=10),表示islands有n张牌。

接下来n行，每行输入3个整数cost(0<=cost<=10),d(0或者1)，w(|w|<=1000)。其中cost表示该牌的法力值消耗，如果d=0，表示该牌是攻击力w的随从牌。如果d=1，表示是能给一个随从增加w攻击的法术牌。

【输出格式】

输出一行表示答案。

【样例输入】

1

1 0 100

【样例输出】

100

二。解法

【二进制枚举】n张牌，枚举每张牌取还是不取。

地址：https://www.oj.swust.edu.cn/problem/show/2507

#include <iostream>
using namespace std;

int T, n;
int a, b, c;
const int INF = 0x3f3f3f3f;
struct card{
    int cost;
    int d;
    int w;
    card() {};
    card(int _cost, int _d, int _w) {
        cost = _cost, d = _d, w = _w;
    }
} cards[15];
int main() {
    cin >> T;
    for (int cases = 1; cases <= T; cases++) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> a >> b >> c;
            cards[i] = card(a, b, c);
        }
        int maxAttack = 0;
        for (int i = 0; i < (1<<n); i++) {
            int nowAttack = 0;
            int MP = 10;
            bool haveServant = false;
            for (int j = 0; j < n; j++) {
                if (i & (1 << j)) { //如果使用第j张牌
                    MP -= cards[j].cost;
                    nowAttack += cards[j].w;
                    if (cards[j].d == 0) haveServant = true;
                }
            }
            if (MP < 0) continue;
            if (haveServant) {
                maxAttack = max(maxAttack, nowAttack);
            }
        }
        cout << "Case #" << cases << ": " << maxAttack << endl;
    }

    return 0;
}

三。给一组数据，帮你debug

/* 
Input:
2

0

5
3 0 -100
3 1 101
2 0 -100
5 1 300
2 1 -100

Output:
Case #1: 0
Case #2: 301

*/

四。DFS写法

#include <iostream>
#include <cstring>
using namespace std;
int T, n;
struct cardS{
    int c, d, w;
}cards[15];
bool vis[15];
int ans = 0;
bool haveServant = false;
void dfs(int cost,int attack) {
    if (cost < 0) return;
    if (haveServant) {
        ans = max(ans, attack);
    }
    for (int i = 0; i < n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            if (cards[i].d == 0) haveServant = true;

            dfs(cost - cards[i].c, attack + cards[i].w);

            vis[i] = false;
            haveServant = false;
            for (int j = 0; j < n; j++) {
                if (vis[j] && cards[j].d == 0) {
                    haveServant = true;
                }
            }
        }
    }
}
int main() {
    cin >> T;
    for (int t = 1; t <= T; t++) {
        cin >> n;
        for (int i = 0; i < n; i++) {
            cin >> cards[i].c >> cards[i].d >> cards[i].w;
        }
        ans = 0;    //注意ans要修改为0，否则影响下一组数据。
        dfs(10, 0);
        cout << "Case #" << t << ": " << ans << endl;
    }
    return 0;
}