【NOIP2016普及组复赛模拟赛】买装备

题目描述

mxy 沉迷于一个辣鸡游戏不可自拔。

为了加强角色的实力，mxy 决定重新买一套装备。

已知现在有 n 件装备，每件装备会提供一定的物理抗性和魔法抗性，并需要一定的价钱。

mxy 想要保证至少有 a 的物抗和 b的魔抗，请你计算出满足条件所需的最少金额。

（装备不可重复购买）

输入

第一行两个整数 a，b 表示最少需要的物抗和魔抗。

（1≤a≤21，1≤b≤79）
第二行为整数 n （1≤n≤21）表示装备的个数。

此后的 n 行，每行包括 ai，bi，mi（1≤ai≤21，1≤bi≤79,1≤mi≤800）3 整数，这
些各自是：第 i 件装备的物抗、魔抗和价钱。

输出

一行一个整数，表示满足条件的最小金额。

样例输入

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
（说明：选 1，2 或者 4，5 号装备）

样例输出

249

纯纯的背包，只不过多了一个元素

大致思路：

判断两种元素是否合法，合法则取money最小值，递归买或不买两种情况就OK了

/声明下，看完文章要点赞，抄袭一经发现后果自负/

代码如下：

#include 
using namespace std;
int a, b, n, ans = 99999999;
int q[21][3];

void dg(int aa, int ab, int money, int step)
{
	if (step > n)
		return ;
	if (aa >= a && ab >= b)
		{
			ans = min(ans, money);
			return ;
		}
	dg(aa + q[step][0], ab + q[step][1], money + q[step][2], step + 1);
	dg(aa, ab, money, step + 1);
}

main()
{
	freopen("equipment.in", "r", stdin);
	freopen("equipment.out", "w", stdout);
	scanf("%d%d%d", &a, &b, &n);
	for (int i = 0; i < n; i++)
		{
			for (int j = 0; j < 3; j++)
				{
					scanf("%d", &q[i][j]);
				}
		}
	dg(0, 0, 0, 0);
	printf("%d", ans);
}