poj 2441(状压DP)

poj 2441

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

#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;
}