2016CCPC Final H. Engineer Assignment

题目大意

\(T(1\leq T\leq 100)\) 组数据。 \(n(1\leq n\leq 10)\) 个项目， \(m(1\leq m\leq 10)\) 个工程师，每个项目需要 \(C_{i}(1\leq C_{i}\leq 3)\) 种技术，第 \(i\) 个项目所需要的技术用 \(a_{i,j}(1\leq a_{i,j}\leq 100)\) 来表示；每个工程师可以负责 \(D_{i}(1\leq D_{i}\leq2)\) 种技术，第 \(i\) 个工程师能负责的技术用 \(b_{i,j}(1\leq b_{i,j}\leq 100)\) 来表示，一个项目可以有多个工程师参与，仅当当所有参与该项目的工程师能够负责的技术能够包含该项目所需要的技术时，该项目可以被完成；而一个工程师只能参与一个项目，求出可以完成的最大项目数。

思路

因为工程师的数量很小，我们考虑状压来表示目前工程师们的使用状况，可以预先处理出 \(can[i,sta]\) 表示在各种使用状况下，第 \(i\) 个项目是否能够完成。
之后我们用背包的方法进行 \(dp\) ，记 \(dp[i,sta]\) 为考虑前 \(i\) 个项目，工程师目前的使用状态为 \(sta\) 时，可以完成的最大项目数，于是我们可以枚举 \(sta\) 的所有子集 \(sub\) ，于是有：

\(dp\) 的初始值都为 \(0\) ，最后答案遍历 \(dp[n][sta]\) 取最小值即可。

代码

#include
#include
#include
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
#define all(x) x.begin(),x.end()
//#define int LL
//#define lc p*2+1
//#define rc p*2+2
#define endl '\n'
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#pragma warning(disable : 4996)
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
const double eps = 1e-8;
const LL MOD = 1000000007;
const LL mod = 998244353;
const int maxn = 15;

int T, N, M, cnt = 0, C[maxn], D[maxn];
int p[maxn][4], e[maxn][3];
int dp[maxn][1 << maxn];
bool can[maxn][1 << maxn];
mapmp;

void solve()
{
	for (int i = 0; i < (1 << M); i++)
	{
		mp.clear();
		for (int j = 0; j < M; j++)
		{
			if ((i >> j) & 1)
			{
				for (int k = 1; k <= D[j+1]; k++)
					mp[e[j + 1][k]]++;
			}
		}
		for (int j = 1; j <= N; j++)
		{
			for (int k = 1; k <= C[j]; k++)
			{
				if (!mp[p[j][k]])
				{
					can[j][i] = false;
					break;
				}
				if (k == C[j])
					can[j][i] = true;
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		for (int j = 0; j < (1 << M); j++)
		{
			int k = j;
			do
			{
				dp[i][j] = max(dp[i][j], dp[i - 1][k] + (int)can[i][j ^ k]);
				k = (k - 1) & j;
			} while (k != j);
		}
	}
	int ans = 0;
	for (int i = 0; i < (1 << M); i++)
		ans = max(ans, dp[N][i]);
	cout << "Case #" << cnt << ": " << ans << endl;
}

int main()
{
	IOS;
	cin >> T;
	while (T--)
	{
		memset(dp, 0, sizeof(dp));
		cnt++;
		cin >> N >> M;
		for (int i = 1; i <= N; i++)
		{
			cin >> C[i];
			for (int j = 1; j <= C[i]; j++)
				cin >> p[i][j];
		}
		for (int i = 1; i <= M; i++)
		{
			cin >> D[i];
			for (int j = 1; j <= D[i]; j++)
				cin >> e[i][j];
		}
		solve();
	}

	return 0;
}