poj 2441(状压DP)

poj 2441

用二进制来表示每个牛棚进棚情况。
设$dp(i, S)$为第$i$只奶牛$S$状态的总方案数。
则状态转移方程为
$$dp(i, S) += dp(i-1, S-j)$$
其中$j$在$S$中且$j$被$i$奶牛喜欢。
本来不想压滚动数组,但是会MLE,无奈只能压了,注意$S$就要倒过来求值了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 20 + 2;
int n, m, dp[1<<20], fav[MAXN][MAXN];
bool check(int x) {
int ans = 0;
while (x) {
ans++;
x&=(x-1);
}
return ans == n;
}
void clean() {
ms(fav, -1), ms(dp, 0), dp[0] = 1;
}
void solve() {
clean();
for (int i=1;i<=n;i++) {
int p; scanf("%d", &p);
for (int j=1;j<=p;j++) scanf("%d", &fav[i][j]);
}
for (int hi=1;hi<=n;hi++) {
for (int S=(1<<m);S>0;S--) {
for (int orz=1;fav[hi][orz]!=-1;orz++) {
int i = fav[hi][orz];
if (S&(1<<(i-1))) {
dp[S] += dp[S^(1<<(i-1))];
}
}
}
}
int ans = 0;
for (int S=1;S<(1<<m);S++) {
if (check(S)) {
ans += dp[S];
}
}
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &n, &m)==2) solve();
return 0;
}

------ 本文结束 ------