公牛队:农夫约翰有N支公牛队,分别独占M个球场中的若干个,求分配方案的个数?
3.4熟练掌握动态规划
状态压缩DP
白天写代码混饭,晚上写代码寻欢。
基本上是个带记忆的枚举,难点在对集合状态的枚举上。我第一次是这么干的:
#include <iostream> #include <vector> using namespace std; #define MAX_N 20 #define MAX_M 20 vector<int> dp[2]; // dp[now]表示满足了i的情况下剩下场地构成的集合S vector<int> barn[MAX_N]; // 每个球队喜欢的球场 ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int N, M; cin >> N >> M; for (int i = 0; i < N; ++i) { int P; cin >> P; barn[i].reserve(P); for (int j = 0; j < P; ++j) { int b; cin >> b; --b; barn[i].push_back(b); } } int S = (1 << M) - 1; for (int i = 0; i < barn[0].size(); ++i) { dp[0].push_back(S & ~(1 << barn[0][i])); } for (int i = 1; i < N; ++i) { int pre = (i - 1) & 1; int now = i & 1; dp[now].clear(); for (int j = 0; j < barn[i].size(); ++j) { for (int k = 0; k < dp[pre].size(); ++k) { if (dp[pre][k] >> barn[i][j] & 1) { dp[now].push_back(dp[pre][k] & ~(1 << barn[i][j])); } } } } cout << dp[(N - 1) & 1].size() << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
结果MLE了,而且这里肯定不能用vector的,最后vector里面都是相同的S,估计应该用map记录S和出现的次数,可以省点内存。这里如果会枚举子集的话就相当省了:
基本枚举:
枚举子集:
定义 dp[S] := 当场地集合为S时,每个球队都不冲突的情况种数。
那么 dp[1 << (第一个球队喜欢的场地编号)] = 1
递推方法是,从第i个球队开始,枚举集合{0, 1, … , M – 1}的大小为i的子集,也就是分配了i个场地,满足了i个球队,如果球队i喜欢场地j并且j不在集合S中,那么dp[S ∪ j] += dp[S]。
#include <iostream> #include <bitset> using namespace std; #define MAX_N 20 #define MAX_M 20 int dp[1 << MAX_M]; // dp[S]表示已分配场地构成的集合S时的情况种数 bool like[MAX_N][MAX_M]; // like[i][j]表示球队i喜欢场地j ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int N, M; cin >> N >> M; for (int i = 0; i < N; ++i) { int P; cin >> P; for (int j = 0; j < P; ++j) { int b; cin >> b; --b; like[i][b] = true; } } for (int i = 0; i < M; ++i) { if (like[0][i]) { dp[1 << i] = 1; // 将i场地分配给0号球队 } } for (int i = 1; i < N; ++i) { for (int comb = (1 << i) - 1, x, y; comb < (1 << M); x = comb & -comb, y = comb + x, comb = ((comb & ~y) / x >> 1) | y) { // comb表示集合{0, 1, ... , M - 1}的大小为i的子集,也就是分配了i个场地,满足了i个球队 if (dp[comb]) { for (int j = 0; j < M; ++j) { if (like[i][j] && !((comb >> j) & 1)) { // i需要j并且j没有被分配,此时将j分配掉 dp[comb | (1 << j)] += dp[comb]; } } } } } int result = 0; for (int bit = 0; bit < (1 << M); ++bit) { if (bitset<32>(bit).count() == N) { result += dp[bit]; } } cout << result << endl; #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif return 0; } ///////////////////////////End Sub//////////////////////////////////
13253776 | hankcs | 2441 | Accepted | 4356K | 172MS | C++ | 1476B | 2014-08-06 03:47:55 |
知识共享署名-非商业性使用-相同方式共享:码农场 » POJ 2441 Arrange the Bulls 题解 《挑战程序设计竞赛》