poj 2441 Arrange the Bulls (状态压缩dp+滚动数组)-白红宇

poj 2441 Arrange the Bulls (状态压缩dp+滚动数组)

阅读量：6417 次

发布时间：2019-06-23

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

题意：

n头牛和m个barn，每头牛有自己喜欢的p个barn(1<=p<=m)，问有多少种安排n头牛的方法。

分析：

dp[i][j]表示i头牛在j状态下的方法数。

dp[i][j] = sigma(dp[i-1][k]) (k从0到 1<<m)。

要用滚动数组优化，否则dp[20][1<<20]会MLE！

注意滚动数组的清空= =！

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              10 #include
               
                11 12 using namespace std;13 14 typedef long long ll;15 16 vector
                
                  p[25];17 int dp[2][1<<20],n;18 19 int main()20 {21 int m,x,y;22 while(~scanf("%d%d",&n,&m))23 {24 for(int i=1;i<=n;i++)25 {26 p[i].clear();27 scanf("%d",&x);28 while(x--)29 {30 scanf("%d",&y);31 p[i].push_back(y);32 }33 }34 memset(dp,0,sizeof(dp));35 36 int all = (1<
                 
                  >t)&1) continue; //如果k状态下这个位置已经有牛则不能放49 dp[i&1][k|(1<