蓝桥杯2019年第十届真题-糖果-题解（C++代码）

constexpr auto Inf = 0X3F3F3F3F;
#ifndef LOCAL
	#include <bits/stdc++.h>
#endif

typedef long long LL;
using namespace std;

namespace IO {
	inline LL read() {
		LL o = 0, f = 1; char c = getchar();
		while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
		while (c > '/' && c < ':') { o = o * 10 + c - '0'; c = getchar(); }
		return o * f;
	}
	inline char recd() {
		char o; while ((o = getchar()) < '0' || o > '9'); return o;
	}
	inline double reod() {
		double o = read(), f = 1; char c;
		while ((c = getchar()) > '/' && c < ':') o += (c - '0') / (f *= 10);
		return o;
	}
}
using namespace IO;

const int SIZE = 1E3 + 7, Mod = 1E9 + 7;

int DP[1 << 21], a[SIZE];

int main() {
	int N = read(), M = read(), K = read(); memset(DP, Inf, sizeof DP), DP[0] = 0;
	for (int pos = 1; pos <= N; pos++) 
		for (int v = 1; v <= K; v++)
			a[pos] |= 1 << (read() - 1);

	for (int pos = 1; pos <= N; pos++) {
		for (int S = (1 << M) - 1; ~S; S--)
			DP[S | a[pos]] = min(DP[S | a[pos]], DP[S] + 1);
	}
	printf("%d\n", DP[(1 << M) - 1] == Inf ? -1 : DP[(1 << M) - 1]);
}