[poj2441] Arrange the Bulls-白红宇

[poj2441] Arrange the Bulls

阅读量：6828 次

发布时间：2019-06-26

本文共 1640 字，大约阅读时间需要 5 分钟。

题意：

n头公牛，m个仓库，每个公牛有一些自己喜欢的仓库，求每个公牛单独住进仓库的方案数。

题解：

状压dp，滚一维，两种写法，实测第一种写法要快些......

滚掉第一维

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define N 21#define RG registerusing namespace std;int dp[1<
          
           '9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}int main() { RG int n=gi(),m=gi(),ans=0; for(RG int i=1; i<=n; i++) { ve[i][0]=gi(); for(RG int j=1; j<=ve[i][0]; j++) { ve[i][j]=gi(); } } dp[0]=1; for(RG int i=1; i<=n; i++) { for(RG int j=(1<
           
            =0; j--) { if(!dp[j]) continue;//强力剪枝 for(RG int k=1; k<=ve[i][0]; k++) { if(j&(1<<(ve[i][k]-1))) continue; dp[j|(1<<(ve[i][k]-1))]+=dp[j]; } dp[j]=0; } } for(RG int j=0; j<1<

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define ll long long#define N 21#define RG registerusing namespace std;int dp[2][1<
          
           '9')) ch=getchar(); if(ch=='-') o=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar(); return o*x;}int main() { RG int n=gi(),m=gi(),ans=0,now=0; for(RG int i=1; i<=n; i++) { ve[i][0]=gi(); for(RG int j=1; j<=ve[i][0]; j++) { ve[i][j]=gi(); } } dp[now][0]=1; for(RG int i=1; i<=n; i++) { now^=1; for(RG int j=(1<
           
            =0; j--) { if(!dp[now^1][j]) continue;//强力剪枝 for(RG int k=1; k<=ve[i][0]; k++) { if(j&(1<<(ve[i][k]-1))) continue; dp[now][j|(1<<(ve[i][k]-1))]+=dp[now^1][j]; } dp[now^1][j]=0; } } for(RG int j=0; j<1<