计蒜客：islands 打炉石传说

1.子集枚举

子集枚举

2. 题目

（在网上没有找到原题，这是计蒜客ACM训练营，第一章的最后一题）

3.思路

枚举要出的牌，i 中的 1 的个数就是要出多少张牌，1 的位置就是要出那张牌的位置，vis[] 数组记录

记得要排序，把攻击值 大 的牌 ，放在前面，如果攻击值相同， 把花费少的 牌 放前面，这样好贪心。

首先，一定要出一张随从牌（题目要求），然后对于法术牌 和 随从牌 我们不加以区分，也就是对他们同样看待

我们只关注 最终的 攻击值 t。

之后，就是在 水晶容许的情况下 （初始化为10） ，**尽可能 **的把 能力值 w 为 正数的牌出完，

对于每个 枚举的 **i ** 得出的能力值 t ，与最大值进行更新， 答案就是 maxi

4.AC代码

#include <bits/stdc++.h>
using namespace std;
struct node{
    int cost,d,w;
}p[20];
bool vis[20];
bool cmp(node a,node b){
    if(a.w != b.w ) return a.w > b.w;
    else if(a.w == b.w) return a.cost < b.cost;
}
int main(){
    int n,cnt = 0;
    cin>>n;
    for(int i = 0;i < n; ++i){
        cin>>p[i].cost>>p[i].d>>p[i].w;
    }
    int bitk = (1 << n),bitkk = (1 << cnt);
    sort(p,p+n,cmp);
    int my = 10,maxi = -1,t = 0,flag1 = 0;
    for(int i = 0;i < bitk; ++i){//枚举子集
        t = 0;//初始 攻击力 为 0
        my = 10;//初始 水晶 为 10
        flag1 = 0;//第一张牌 一定要出随从
        memset(vis,0,sizeof(vis));
        for(int j = 0;j < n; ++j){
            if(i & (1<<j)){//找到要处理的 牌
                vis[j] = 1;
            }
        }
        for(int j = 0;j < n; ++j){
            if(vis[j] && p[j].d == 0){//找出第一张 随从牌
                vis[j] = 0;
                my -= p[j].cost;
                t += p[j].w;
                flag1 = 1;
                break;
            }
        }
        if(flag1 == 1){//如果找到第一章随从牌，就继续出牌
            for(int j = 0;j < n; ++j){
                if(my < 0) break;//水晶不够  就跳出来
                if(vis[j] && p[j].w > 0 && my >= p[j].cost &&flag1 == 1){
                    my -= p[j].cost;
                    t += p[j].w;
                    vis[j] = 0;
                }
            }
        }
        maxi = max(maxi,t);//更新 最大值
    }
    cout<<maxi;
    return 0;
}

5. 几组数据 和 坑点

第十组样例

10
1 0 200
2 0 300
3 0 499
4 1 -1000
6 1 10
5 1 24
3 1 0
10 1 1000
6 1 100
10 0 998

坑点

• 会出现花费为 0 的牌
• 会出现w 为负值的牌
• 第一个选取的 能力值最高的随从 ，不一定是正确答案，比如上面的第十组数据
• 可能会 没有 随从牌， 也就是 ，你的攻击力可能一直 为 0，flag1