http://acm.split.hdu.edu.cn/showproblem.php?pid=6006
比赛的时候写了一个暴力，存暴力，过了，还46ms
那个暴力的思路是，预处理can[i][j]表示第i个人能否胜任第j个项目，能胜任的条件就是它和这个项目有共同的需求。
然后暴力枚举每一个人去搭配哪一个项目，
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
#define X first
#define Y second
#define clr(u,v); memset(u,v,sizeof(u));
#define inff() freopen("data","r",stdin);
#define out() freopen("ans","w",stdout);
#define Clear(Q); while (!Q.empty()) Q.pop();
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long LL;
typedef pair <int, int> pii;
const LL INF = 1e17;
const int inf = 0x3f3f3f3f;
const int maxn = 1e2 + ;
vector<int> project[maxn], man[maxn];
int e[maxn][maxn], DFN;
bool can[][];
int n, m; // n_project, m_man
int has[][maxn];
bool need[][maxn];
int ans = ;
void dfs(int cur) {
if (cur == m + ) {
int t = ;
for (int i = ; i <= n; ++i) {
bool flag = true;
for (int j = ; j < project[i].size(); ++j) {
if (!has[i][project[i][j]]) {
flag = false;
break;
}
}
t += flag;
}
ans = max(ans, t);
return;
}
// bool can = false;
for (int i = ; i <= n; ++i) {
if (!can[cur][i]) continue;
bool flag = false;
for (int j = ; j < man[cur].size(); ++j) {
if (!need[i][man[cur][j]]) continue;
if (has[i][man[cur][j]]) continue;
flag = true;
break;
}
if (!flag) continue;
for (int j = ; j < man[cur].size(); ++j) {
has[i][man[cur][j]]++;
}
dfs(cur + );
for (int j = ; j < man[cur].size(); ++j) {
has[i][man[cur][j]]--;
}
}
dfs(cur + );
}
void work() {
memset(can, false, sizeof can);
memset(need, false, sizeof need);
memset(has, false, sizeof has);
scanf("%d%d", &n, &m);
++DFN;
for (int i = ; i <= n; ++i) { // project
int c;
scanf("%d", &c);
project[i].clear();
while (c--) {
int val;
scanf("%d", &val);
project[i].push_back(val);
e[i + m][val] = DFN;
need[i][val] = true;
}
}
for (int i = ; i <= m; ++i) { // man
int c;
scanf("%d", &c);
man[i].clear();
while (c--) {
int val;
scanf("%d", &val);
man[i].push_back(val);
e[i][val] = DFN;
}
}
for (int i = ; i <= m; ++i) { // man
for (int j = ; j <= n; ++j) { // project
for (int k = ; k <= ; ++k) { // major
if (e[i][k] == DFN && e[j + m][k] == DFN) {
can[i][j] = true;
break;
}
}
}
}
ans = ;
dfs();
static int f = ;
printf("Case #%d: %d\n", ++f, ans);
} int main()
{
#ifdef LOCAL
inff();
#endif
int T;scanf("%d",&T);
while(T--)
{
work();
}
return ;
}
正解是状压dp
其实是一个挺好想的dp
dp[i][1 << m]表示处理了前i个项目，状态是j的时候的最大完成数目。
首先预处理要完成第i个项目，状态k是否可行。然后类似于背包
给定状态s，去除子状态k后，就能完成第i项目了，所以dp[i][s] = max(dp[i][s], dp[i - ][s - k] + 1);
dp[i - 1][s - k] + 1表示用状态s - k去完成前i - 1个项目，能完成多少。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
#define X first
#define Y second
#define clr(u,v); memset(u,v,sizeof(u));
#define inff() freopen("data","r",stdin);
#define out() freopen("ans","w",stdout);
#define Clear(Q); while (!Q.empty()) Q.pop();
#define pb push_back
using namespace std;
typedef long long ll;
typedef long long LL;
typedef pair <int, int> pii;
const LL INF = 1e17;
const int inf = 0x3f3f3f3f;
const int maxn = 1e2 + ;
vector<int> project[maxn], man[maxn];
vector<int> state[maxn];
int solve[][maxn], DFN;
int dp[][ + ];
void work() {
int n, m; // n_project, m_man
scanf("%d%d", &n, &m);
for (int i = ; i <= n; ++i) { // project
int c;
scanf("%d", &c);
project[i].clear();
while (c--) {
int val;
scanf("%d", &val);
project[i].push_back(val);
}
}
for (int i = ; i <= m; ++i) { // man
int c;
scanf("%d", &c);
man[i].clear();
while (c--) {
int val;
scanf("%d", &val);
man[i].push_back(val);
}
}
int en = ( << m) - ;
for (int i = ; i <= n; ++i) {
state[i].clear();
for (int j = ; j <= en; ++j) {
++DFN;
for (int k = ; k <= m; ++k) {
if (j & ( << (k - ))) {
for (int d = ; d < man[k].size(); ++d) {
solve[i][man[k][d]] = DFN;
}
}
}
bool flag = true;
for (int d = ; d < project[i].size(); ++d) {
if (solve[i][project[i][d]] != DFN) {
flag = false;
break;
}
}
if (flag) state[i].push_back(j);
}
}
// for (int i = 1; i <= n; ++i) {
// for (int j = 0; j < state[i].size(); ++j) {
// printf("%d ", state[i][j]);
// }
// printf("\n");
// }
memset(dp, false, sizeof dp);
for (int i = ; i <= n; ++i) {
for (int d = ; d <= en; ++d) {
dp[i][d] = dp[i - ][d]; // 不做这个项目
for (int k = ; k < state[i].size(); ++k) {
if ((d | state[i][k]) > d) continue;
int res = d ^ state[i][k];
dp[i][d] = max(dp[i][d], dp[i - ][res] + );
}
}
}
int ans = ;
for (int i = ; i <= en; ++i) ans = max(ans, dp[n][i]);
static int f = ;
printf("Case #%d: %d\n", ++f, ans);
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
#endif
int T;
scanf("%d", &T);
while(T--) {
work();
}
return ;
}