【蓝桥杯】islands 打炉石传说

题目

islands 最近在完一款游戏“炉石传说”，又名“魔兽英雄传”。

炉石传说是一款卡牌类对战的游戏。

游戏是两人对战，总的来说，里面的卡牌分成两类，一类是法术牌，另一类是随从牌（所谓随从就是怪物）。

为了简化问题，现在假设随从牌的作用是召唤一个具有一定攻击力的怪物，法术牌的作用是给某个随从增加一定攻击力。

随从牌和法术牌的使用都需要消耗一定的法力值。

现在 islands 有 $点法力值，手上有张牌（islands 最多有张牌，否者他将会被爆牌 T_T），有些是法术牌，有些是随从牌。$

islands 现在是大劣势，他想要是利用这 $点法力值使得召唤出来的所有随从的攻击力总和最高（法力值可以不用完）。$

注意，任何法术牌都必须使用在某个召唤出来的随从上，也就是如果 islands 没有召唤过随从，他将不能使用任何法术牌。

告诉 islands 他能召唤的随从的总攻击力最大是多少。

输入格式

每组数据首先输入一个 $\le n \le 10) </annotation> </semantics> </math>$

接下来 $<math> <semantics> <mrow> <mi> n </mi> </mrow> <annotation encoding="application/x-tex"> n </annotation> </semantics> </math> 行，每行输入 <math> <semantics> <mrow> <mn> 3 </mn> </mrow> <annotation encoding="application/x-tex"> 3 </annotation> </semantics> </math> 个整数 <math> <semantics> <mrow> <mi> c </mi> <mi> o </mi> <mi> s </mi> <mi> t </mi> <mo> ( </mo> <mn> 0 </mn> <mo> ≤ </mo> <mi> c </mi> <mi> o </mi> <mi> s </mi> <mi> t </mi> <mo> ≤ </mo> <mn> 10 </mn> <mo> ) </mo> </mrow> <annotation encoding="application/x-tex"> cost(0 \le cost \le 10) </annotation> </semantics> </math>$

其中 $表示该牌的法力值消耗，如果，表示该牌是攻击力为的随从牌；如果，表示是能给一个随从增加攻击的法术牌。$

输出格式

输出一行表示答案。

样例输入

1
1 0 100

样例输出

100

题解

同样是二进制枚举子集
某张牌有两种状态，使用 or 不被使用，分别用二进制的 1 和 0 表示
对所有可使用卡牌情况，如果该位对应为 1 ，累加其最大攻击力，判断其法力值消耗情况和是否存在随从牌

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int cost[10+2],d[10+2],w[10+2];
	int Max = 0;
	for(int i=0;i<n;i++)
		cin>>cost[i]>>d[i]>>w[i];
	for(int i=0;i<(1<<n);i++){
		int sum = 0;
		int magic = 10;
		bool flag = false;   // 随从 
		for(int j=0;j<n;j++){
			if(i & (1 << j)){
				if(!d[j])
					flag = true;
				sum += w[j];
				magic -= cost[j];
			}
		}
		if(flag && magic >= 0 )
			Max = max(sum,Max);
	}
	cout<<Max;
	return 0;
}

返回目录，查看更多