HDU - 6006 Engineer Assignment（状压dp）

本文主要是介绍HDU - 6006 Engineer Assignment（状压dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题意：有 $n$ 个任务，完成这些任务需要一些领域的知识。有 $m$ 个工程师，每个工程师都有一些自己会的领域。每个工程师只能选择一个任务，若参与这项任务的工程师具备了完成所需的所有知识，这项任务则被完成。问最多能完成几个任务。
题解：题目给的n和m都很小，所以想到了状压 $d p$ 去实现。 $d p [i] [j]$ 表示前 $i$ 个任务在使用工程师 $j$ 状态下最多能完成的任务个数。在维护 $d p$ 状态之前，要额外跑一遍来确定能完成第 $i$ 个任务的方案，用于最后的状态转移。

#include <bits/stdc++.h>
using namespace std;#define endl "\n"int dp[15][1 << 11], c[15], d[15], a[15][15], b[15][15], vis[150];
int n, m, cas;
vector<int> G[15];void solve() {memset(dp, 0, sizeof(dp));cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> c[i];G[i].clear();for (int j = 1; j <= c[i]; ++j) cin >> a[i][j];}for (int i = 1; i <= m; ++i) {cin >> d[i];for (int j = 1; j <= d[i]; ++j) cin >> b[i][j];}for (int i = 1; i <= n; ++i) {for (int j = 0; j < 1 << m; ++j) {memset(vis, 0, sizeof(vis));for (int k = 0; k < m; ++k) {if ((1 << k) & j) {for (int q = 1; q <= d[k + 1]; ++q) {vis[b[k + 1][q]] = 1;}}}for (int q = 1; q <= c[i]; ++q) {if (!vis[a[i][q]]) break;if (q == c[i]) G[i].push_back(j);}}}for (int i = 1; i <= n; ++i) {for (int j = 0; j < 1 << m; ++j) {dp[i][j] = dp[i - 1][j];//注意这步状态转移for (auto v : G[i]) {if ((v & j) != v) continue;dp[i][j] = max(dp[i - 1][j - v] + 1, dp[i][j]);}}}cout << "Case #" << ++cas << ": " << dp[n][(1 << m) - 1] << endl;
}
int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int _T;cin >> _T;while (_T--) solve();return 0;
}