POJ 2441 Arrange the Bulls 状态压缩递推简单题（状态压缩DP）

里面有状态压缩论文的链接，可以看看。

该解题报告中用的是二维数组，但是很显然的是，递推式中的下一行只与上一行有关，类似于最长公共子序列，可以用滚动数组，在滚动数组后发现只用一个数组就可以了。至于是不是要和0-1背包一样得按从大到小的顺序，我没有，我的状态是从小到大的顺序，但是也AC了。

如果不用滚动数组，会超内存。

自己动手退一下，就能从滚动数组推到只用一个数组的情形。

然后我就直接贴我的代码，注释就在代码中

 1 #include <cstdio>
 2 #include <cstring>
 3 int dp[(1<<20)+2];
 4 int one[(1 << 20) + 2];
 5 //用来数出状态为i时1的个数，具体到这个题中就是
 6 //状态为i时有多少头牛已经安排好牛棚
 7 void CountOne(int m)
 8 {
 9     for(int i=0; i< (1 << m); ++i)
10     {
11         int num=0;
12         for(int j=0; j< m; ++j)
13         {
14             if( (i & (1 << j)) != 0)
15                 ++num;
16         }
17         one[i] = num;
18     }
19 }
20 int main()
21 {
22 //    freopen("in.cpp","r",stdin);
23     int n,m;
24     scanf("%d%d",&n,&m);
25     CountOne(m);
26     memset(dp,0,sizeof(dp));
27     dp[0] = 1; //一头牛都没有安排，状态为0的满足条件的方案数为1
28     for(int i=1; i<=n; ++i)
29     {
30         int cnt; //每头牛喜欢住的牛棚数
31         scanf("%d",&cnt);
32         while(cnt--)
33         {
34             int k; //该牛棚编号
35             scanf("%d",&k);
36             --k;//使得牛棚编号为 0 ~ m-1
37             for(int j=0; j< (1 << m); ++j)
38             {
39                 if((j & (1 << k)) != 0 && one[j] == i) //这个状态已经安排好了i头牛，且第k个牛棚安排的是第i头牛
40                     dp[j] += dp[j-(1<<k)];
41             }
42         }
43     }
44     // 最终结果为安排了n头牛的状态满足条件的方案数的总和
45     int ans=0;
46     for(int j=0; j< (1 << m ); ++j)
47     {
48         if(one[j] == n)
49         {
50             ans += dp[j];
51         }
52     }
53     printf("%d
",ans);
54     return 0;
55 }

View Code

POJ 2441 Arrange the Bulls 状态压缩递推简单题 （状态压缩DP）

POJ 2441 Arrange the Bulls 状态压缩递推简单题（状态压缩DP）