当前位置 博文首页 > Keven_11的博客:C++题解:islands打炉石传说
??????目录
题目?
题解
- ?1000ms
- ?131072K
islands 最近在玩一款游戏“炉石传说”,又名“魔兽英雄传”。炉石传说是一款卡牌类对战的游戏。游戏是两人对战,总的来说,里面的卡牌分成两类,一类是法术牌,另一类是随从牌(所谓随从就是怪物)。
为了简化问题,现在假设随从牌的作用是召唤一个具有一定攻击力的怪物,法术牌的作用是给某个随从增加一定攻击力。随从牌和法术牌的使用都需要消耗一定的法力值。现在 islands 有?10?点法力值,手上有?nn?张牌(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?攻击的法术牌。
输出格式
输出一行表示答案。
输出时每行末尾的多余空格,不影响答案正确性
要求使用「文件输入输出」的方式解题,输入文件为?
stone.in
,输出文件为?stone.out
样例输入
1 1 0 100
样例输出
100
题解:
知识点:二进制枚举子集
分析:?二进制暴力枚举,最后判断
代码:
cs#include<iostream> #include<cstdio> #define _for(i,a,b) for (int i=(a);i<(b);i++) using namespace std; const int N=20; struct magic{ int cost,w; bool d; }a[N]; int main(){ freopen("stone.in","r",stdin); freopen("stone.out","w",stdout); int n,ans=0; cin>>n; _for(i,0,n){ cin>>a[i].cost>>a[i].d>>a[i].w; } _for(i,0,1<<n){//二进制枚举子集,表示是否选了此东西,1表示选 bool d=false; int cost=0,w=0; _for(j,0,n){ if (i&(1<<j)){ cost+=a[j].cost; if (!a[j].d){//判断有没有随从牌 d=true; } w+=a[j].w; } } if (d && cost<=10){ ans=max(ans,w); } } cout<<ans<<endl; return 0; }
下一篇:没有了