[蓝桥杯 2019 省 A] 糖果-EW帮帮网

一.题目

题目描述

糖果店的老板一共有 M 种口味的糖果出售。

为了方便描述，我们将 M 种口味编号 1∼M。

小明希望能品尝到所有口味的糖果。

遗憾的是老板并不单独出售糖果，而是 K 颗一包整包出售。

幸好糖果包装上注明了其中 K 颗糖果的口味，所以小明可以在买之前就知道每包内的糖果口味。

给定 N 包糖果，请你计算小明最少买几包，就可以品尝到所有口味的糖果。

输入格式

第一行包含三个整数 N,M,K。

接下来 N 行每行 K 个整数 $T_1,T_2,⋅⋅⋅,T_K$ ，代表一包糖果的口味。

输出格式

一个整数表示答案。

如果小明无法品尝所有口味，输出 −1。

数据范围

1 ≤ N ≤ 100,
1 ≤ M , K ≤ 20,
1 ≤ $T_i$ ≤ M

输入样例

6 5 3
1 1 2
1 2 3
1 1 3
2 3 5
5 4 2
5 1 2

输出样例

二.解释

看完题目，首先想到的是直接暴力，我们有 N 包糖果，每包糖果都有选和不选两种状态，写循环显然不可能，那用递归，每重递归处理某包糖果的两种情况。N 包就有 N 重递归，包含大量重复计算，复杂度太高，只能解部分样例。

在判断每包糖果的选与不选的时候，都是基于之前已经处理的情况来决定：

1.当前面的的某种选择情况已经包含这包糖果的所有口味，自然不用选择；

2.当前面的的某种选择情况没有包含这包糖果的所有口味：

设之前已经包含的所有口味为集合 A，当前糖果所有口味为集合 B，这是我们只需要比较之前包含**（A U B）**口味的糖果包数量和集合 A 选择的糖果包数量 + 1的较小值。

此时我们可以用DP的方法来做，对于每种口味，我们用一个位来表示选（1）与不选（0）：
设有 DP 数组，对于下表 i，i 的二进制位的前 N 位表示 N 包糖果的状态；

则有DP[i]：口味包含情况为 i 所需的最小糖果包数量。

三.代码

1.暴力递归:

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <set>

using namespace std;

const int MaxN = 110;

int InN, InM, InK, Res = 0x3f3f3f3f;	//糖果包总数，口味总数，每包的口味数
unordered_map<int, int> Map[MaxN];		//记录已经包含的口味

void Get(int InI, int InC, unordered_map<int, int> InH)
{
	if (InH.size() == InM)
	{
		Res = min(Res, InC);
		return;
	}
	if (InI > InN)
	{
		if (InH.size() == InM)
		{
			Res = min(Res, InC);
		}
		return;
	}

	//不选
	Get(InI + 1, InC, InH);
	
	//选
	unordered_map<int, int> Tmp = InH;
	InH.insert(Map[InI].begin(), Map[InI].end());	//把这包糖果的口味加到集合
	Get(InI + 1, InC + 1, InH);
	//回溯
	InH = Tmp;
}

int main()
{
	cin >> InN >> InM >> InK;

	int a;
	for (int i = 1; i <= InN; i++)
	{
		for (int j = 1; j <= InK; j++) { scanf("%d", &a); Map[i][a]++; }
	}

	unordered_map<int, int> InH;
	Get(1, 0, InH);

	cout << Res;

	return 0;
}

2.DP：

#include <iostream>
#include <unordered_map>
#include <algorithm>
#include <cstring>
#include <set>

using namespace std;

const int MaxN = 110;

int InN, InM, InK, Res = 0x3f3f3f3f;	//糖果包总数，口味总数，每包的口味数
int Ns[MaxN];							//记录每包糖果包含的口味
int DP[1 << 21];						//最多20种口味，最少需要20位。多开一个保险，记录包含口味的最小包数

int main()
{
	cin >> InN >> InM >> InK;

	int a;
	for (int i = 1; i <= InN; i++)
	{
		//使用按位或（|），记录口味
		for (int j = 1; j <= InK; j++) { scanf("%d", &a); Ns[i] |= 1 << (a - 1); }
	}

	memset(DP, 0x3f, sizeof DP);

	DP[0] = 0;
	for (int i = 1; i <= InN; i++)
	{
		for (int j = 0; j <= 1 << InM; j++)
		{
			//大于N买不到所有口味，跳过
			if (DP[j] > InN) continue;
			//已经有j口味，或上Ns[i]表示加上这包糖果的口味
			DP[j | Ns[i]] = min(DP[j | Ns[i]], DP[j] + 1);
		}
	}
	
	//以5种口味为例，1 << 5为100000，减一后为11111，表示物种口味全选
	//当包含所有口味的包数大于N的时候返回-1，否则直接返回结果
	if (DP[(1 << InM) - 1] > InN) { cout << -1; }
	else { cout << DP[(1 << InM) - 1]; }

	return 0;
}

[蓝桥杯 2019 省 A] 糖果