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 + 2; vector<int> project[maxn], man[maxn]; int e[maxn][maxn], DFN; bool can[12][12]; int n, m; // n_project, m_man int has[12][maxn]; bool need[12][maxn]; int ans = 0; void dfs(int cur) { if (cur == m + 1) { int t = 0; for (int i = 1; i <= n; ++i) { bool flag = true; for (int j = 0; 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 = 1; i <= n; ++i) { if (!can[cur][i]) continue; bool flag = false; for (int j = 0; 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 = 0; j < man[cur].size(); ++j) { has[i][man[cur][j]]++; } dfs(cur + 1); for (int j = 0; j < man[cur].size(); ++j) { has[i][man[cur][j]]--; } } dfs(cur + 1); } 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 = 1; 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 = 1; 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 = 1; i <= m; ++i) { // man for (int j = 1; j <= n; ++j) { // project for (int k = 1; k <= 100; ++k) { // major if (e[i][k] == DFN && e[j + m][k] == DFN) { can[i][j] = true; break; } } } } ans = 0; dfs(1); static int f = 0; printf("Case #%d: %d ", ++f, ans); } int main() { #ifdef LOCAL inff(); #endif int T;scanf("%d",&T); while(T--) { work(); } return 0; }
正解是状压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 + 2; vector<int> project[maxn], man[maxn]; vector<int> state[maxn]; int solve[12][maxn], DFN; int dp[12][1024 + 2]; void work() { int n, m; // n_project, m_man scanf("%d%d", &n, &m); for (int i = 1; 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 = 1; 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 = (1 << m) - 1; for (int i = 1; i <= n; ++i) { state[i].clear(); for (int j = 1; j <= en; ++j) { ++DFN; for (int k = 1; k <= m; ++k) { if (j & (1 << (k - 1))) { for (int d = 0; d < man[k].size(); ++d) { solve[i][man[k][d]] = DFN; } } } bool flag = true; for (int d = 0; 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(" "); // } memset(dp, false, sizeof dp); for (int i = 1; i <= n; ++i) { for (int d = 1; d <= en; ++d) { dp[i][d] = dp[i - 1][d]; // 不做这个项目 for (int k = 0; 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 - 1][res] + 1); } } } int ans = 0; for (int i = 1; i <= en; ++i) ans = max(ans, dp[n][i]); static int f = 0; printf("Case #%d: %d ", ++f, ans); } int main() { #ifdef local freopen("data.txt", "r", stdin); #endif int T; scanf("%d", &T); while(T--) { work(); } return 0; }