Arrange the Bulls [POJ2441] [状压DP]

题意

n头牛，m个房间，每头牛有自己喜欢的房间，问每头牛都住进自己喜欢的房间有多少种分配方法？

Input

In the first line of input contains two integers N and M (1 <= N <= 20, 1 <= M <= 20). Then come N lines. The i-th line first contains an integer P (1 <= P <= M) referring to the number of barns cow i likes to play in. Then follow P integers, which give the number of there P barns.

Output

Print a single integer in a line, which is the number of solutions.

Sample Input

Sample Output

Analysis

首先，这种数据我们很容易想到是状压DP

我们可以比较轻松的写出状态转移方程

if(status&(1<<room)==0)

　　dp[i][status|(1<<room)]+=dp[i-1][status];

但是我们发现这样是会MLE的，我们就可以采用滚动数组，或是直接上一维

一维要注意status从大到小循环，因为是每次小的更新大的，status用完之后要清零。

Code

 #include<set>

 #include<map>

 #include<queue>

 #include<stack>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #define RG register int

 #define rep(i,a,b)    for(RG i=a;i<=b;++i)

 #define per(i,a,b)    for(RG i=a;i>=b;--i)

 #define ll long long

 #define inf (1<<29)

 using namespace std;

 int n,m,ans;

 int a[][];

 int dp[];

 inline int read()

 {

     int x=,f=;char c=getchar();

     while(c<''||c>''){if(c=='-')f=-;c=getchar();}

     while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

     return x*f;

 }

 int main()

 {

     n=read(),m=read();

     rep(i,,n)

     {

         a[i][]=read();

         rep(j,,a[i][])

             a[i][j]=read();

     }

     dp[]=;

     rep(i,,n)

     {

         per(j,(<<m)-,)

         {

             if(!dp[j]) continue;

             rep(k,,a[i][])

             {

                 if(!(j&(<<(a[i][k]-))))

                 {

                     dp[j|(<<(a[i][k]-))]+=dp[j];

                 }

             }

             dp[j]=;

         }

     }

     int ans=;

     per(j,(<<m)-,) ans+=dp[j];

     cout<<ans;

     return ;

 }

巴特西

Arrange the Bulls [POJ2441] [状压DP]

最新文章

热门文章