题解 P1879 【[USACO06NOV]玉米田Corn Fields】
ljc20020730
2019-08-10 21:04:51
介绍一个子集枚举的通用算法：
设$Sub$是状态$mask$的子集，那么对于$Sub$中状态所有可能的取值为(含空集)：
```cpp
for (int Sub = mask; ; Sub=(Sub-1) & mask ){
// do sth.
if (!mask) break;
}
```
所以这道题就是一个很明显的状态压缩dp了。
设$f[i][j]$表示前$i$行合法且最后一行的状态是$j$的方案数。
对于这一行状态只和这一行和上一行状态有关系。
枚举这一行状态为$mask1$,上一行状态为$mask2$
- 若本行状态不合理产生的限制为 mask1存在两个连续的1
- 若上一行状态不合理产生的限制为 mask2存在两个连续的1
- 若上一行状态+这一行状态不和里就是mask1和mask2相同位上都有1
对于$1,2$两个限制，我们只需要：
```cpp
if (mask >> 1) return false;
else return true;
```
对于$3$限制，我们只需要
```cpp
if (mask1 & mask2) return false;
else return true;
```
代码就比较简单了：
```cpp
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N=13,mo=100000000;
int f[N][1<<N],n,m,state[N];
signed main()
{
scanf("%lld%lld",&n,&m); int all=(1<<m)-1;
for (int i=1;i<=n;i++) {
int ret=0;
for (int j=1;j<=m;j++) {
int t; scanf("%lld",&t);
ret=(ret<<1)+t;
}
state[i]=ret;
}
for (int mask=state[1] ; ; mask=(mask-1)&state[1] ) {
if (!(mask & (mask>>1))) { f[1][mask]=1; }
if (!mask) break;
}
for (int i=2;i<=n;i++) {
for (int mask1 = state[i]; ;mask1=(mask1-1)&state[i]) {
if (mask1 & (mask1>>1)) continue;
for (int mask2=state[i-1]; ;mask2=(mask2-1)&state[i-1]) {
if (mask2 & (mask2>>1)) continue;
if (mask1 & mask2) continue;
(f[i][mask1]+=f[i-1][mask2])%=mo;
if (!mask2) break;
}
if (!mask1) break;
}
}
int ans=0;
for (int i=0;i<=all;i++) (ans+=f[n][i])%=mo;
printf("%lld\n",ans);
return 0;
}
```