ACM模版
描述
题解
常规的状压 DPDP 套路。
给定 NN 个任务和 MM 个工程师，每个任务都有不超过三个的领域人才需求，每个工程师都有不超过两个领域精通。问在工程师只能使用一次的情况下，最多完成多少任务？
题目的数据很明显的告诉我们要用状压 DPDP，设置 dp[i][j]dp[i][j] 表示前 ii 个任务，工程师选用组合状态为 jj 时的最多完成任务数。这里我们可以先预处理一下每个任务可以由哪些工程师组合来完成，然后在状压 DPDP 的过程中，直接 dp[i][j] = max(dp[i - 1][j ^ vi[i][k]] 1, dp[i][j]);text{dp[i][j] = max(dp[i - 1][j ^ vi[i][k]] 1, dp[i][j]);}，其中 vi[i][k]vi[i][k] 便是上述预处理的结果。难度不大，思路比较常规。
代码
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAXN = 20;
const int MAXM = 10;
const int MAXO = 111;
int N, M;
int vis[MAXO];
int a[MAXN][MAXM];
int b[MAXN][MAXM];
int dp[MAXN][(1 << MAXM) 1];
vector<int> vi[MAXN]; // 第 i 个任务可以由这些状态的工程师集合来完成
void init()
{
memset(dp, 0, sizeof(dp));
for (int i = 1; i <= N; i )
{
vi[i].clear();
}
}
int main()
{
int T;
scanf("%d", &T);
for (int ce = 1; ce <= T; ce )
{
scanf("%d%d", &N, &M);
init();
// N 个工程
for (int i = 1; i <= N; i )
{
scanf("%d", a[i]);
for (int j = 1; j <= a[i][0]; j )
{
scanf("%d", a[i] j);
}
}
// M 个工程师
for (int i = 0; i < M; i )
{
scanf("%d", b[i]);
for (int j = 1; j <= b[i][0]; j )
{
scanf("%d", b[i] j);
}
}
// 预处理，第 i 个任务可以由哪些人完成
for (int i = 1; i <= N; i )
{
int t = 1 << M;
for (int j = 0; j < t; j )
{
int cnt = 0;
memset(vis, 0, sizeof vis);
for (int k = 0; k < M; k )
{
if (j & (1 << k))
{
cnt ;
for (int l = 1; l <= b[k][0]; l )
{
vis[b[k][l]] = 1;
}
}
}
// 任务需求不超过三个人
if (cnt > 3)
{
continue;
}
int flag = 1;
for (int k = 1; k <= a[i][0]; k )
{
if (!vis[a[i][k]])
{
flag = 0;
}
}
if (flag)
{
vi[i].push_back(j);
}
}
}
for (int i = 1; i <= N; i )
{
int t = 1 << M;
for (int j = 0; j < t; j )
{
int sz = (int)vi[i].size();
for (int k = 0; k < sz; k )
{
if ((j | vi[i][k]) == j)
{
dp[i][j] = max(dp[i - 1][j ^ vi[i][k]] 1, dp[i][j]);
}
}
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
}
}
printf("Case #%d: %dn", ce, dp[N][(1 << M) - 1]);
}
return 0;
}
