poj 2441 题意：有N头牛，每头牛都有自己喜欢的barn 而且一个barn只能有一头牛，求给这些牛分配barn 共有多少种方法
#include<bits/stdc++.h> using namespace std; int n,m,x,t; int dp[2][1<<20],a[25][25]; int main(){ scanf("%d%d",&n,&m); memset(a,0,sizeof(a)); memset(dp,0,sizeof(dp)); for(int i = 1;i <= n; ++i){ scanf("%d",&x); while(x--){ scanf("%d",&t); a[i][t] = 1; } } dp[0][0] = 1; for(int i = 1;i <= n; ++i){ for(int j = 0;j < (1 << m); ++j) if(dp[1-i&1][j]){ for(int k = 1;k <= m; ++k){ if(a[i][k] && j != (j|1<<(k-1))){ dp[i&1][j|1<<(k-1)] += dp[1-i&1][j]; } } } memset(dp[1-i&1],0,sizeof(dp[1-i&1])); } int ans = 0; for(int i = 1;i < (1 << m); ++i) ans += dp[n&1][i]; printf("%d\n",ans); return 0; }POJ 2836 题意：农夫有一块地，被划分为m行n列大小相等的格子，其中一些格子是可以放牧的（用1标记），农夫可以在这些格子里放牛，其他格子则不能放牛（用0标记），并且要求不可以使相邻格子都有牛。现在输入数据给出这块地的大小及可否放牧的情况，求该农夫有多少种放牧方案可以选择（注意：任何格子都不放也是一种选择，不要忘记考虑！
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll dp[13][1 << 12]; ll n,m,t; ll b[13],ans; const ll p = 1e9; bool check(ll k){ int x = 0; while(k){ if(k % 2 && x) return 0; x = k % 2; k /= 2; } return 1; } int main(){ scanf("%lld%lld",&n,&m); for(int i = 1;i <= n; ++i){ for(int j = 1; j <= m; ++j){ scanf("%lld",&t); if(!t) b[i] += (1 << (m - j)); } } for(int j = 0;j < (1 << m); ++j) if(check(j) && (j & b[1]) == 0) dp[1][j] = 1; //for(int i = 0;i < (1 << m); ++i) cout<<dp[1][i]<<' '; cout<<endl; for(int i = 2;i <= n; ++i){ ///第i行 for(int j = 0;j < (1 << m); ++j){ if(check(j) && (b[i] & j) == 0){ for(int k = 0;k < (1 << m); ++k){ if(check(k) && (b[i - 1] & k) == 0 && (j & k) == 0){ // cout<<j<<' '<<k<<' '; dp[i][j] = (dp[i][j] + dp[i - 1][k]) % p; // cout<<dp[i][j]<<endl; } } } } } // for(int i =0;i < (1 << m); ++i) cout<<dp[n][i]<<' ';cout<<endl; ans = 0; for(int i = 0;i < (1 << m); ++i) ans = (ans + dp[n][i]) % p; printf("%lld\n",ans); return 0; }
