题解 P1879 【[USACO06NOV]玉米田Corn Fields】
傅思维666
·
·
题解
题解：
推荐博客食用
看到这个数据范围，和这个招牌的01串。应该能想到是状压DP计数的问题。
（话说状压DP就是按数据范围碰？）
那么我们考虑把状态设置成：dp[i][j]表示第i行状态为j的时候的方案数。
现在这道题最让我们无所适从的条件就是判断这块地能不能种草。
我们容易发现：不能种草的情况只有两种：有一些地本来就是荒芜的，不能种草。另外有一些地是因为相邻的地被种上草了所以不能种草。所以我们在转移的时候一定要把判断条件处理好了。
这个怎么去判断呢？
需要高深的位运算知识
- 首先我们开一个数组来存初始状态，即输入时的状态（即F[i]数组），之所以要存储这个初始状态是为了处理本来就荒芜的情况。那么，对于我们当前枚举到的状态j，需要把它和初始状态进行对比。初始状态可以种草的地可以种也可以不种，但是初始状态不可以种草的地绝对不能种。要判断当前状态j合法，只需要把当前状态和F[i]进行对比，如果不让种的地都没种，那么不管可以种的地到底种没种，这个状态都是合法的。
所以我们的判断条件就是j\&F[i]==j。这样的话，如果j在不该种草的地方种上了草（得1），那么它与上0会得0，就不等于j了。
- 然后我们考虑相邻格子，相邻格子有两种：横向相邻和纵向相邻。
显然，如果一个状态合法，在横向上会有010101...这样的情况出现，也就是说对于一个1，它的前一位和后一位肯定是0.那么我们开一个状态数组st[i]。如果它符合“010101...”的条件，那么显然会有：
那么纵向相邻怎么判呢？可以发现，纵向是否相邻是由当前枚举到的状态决定的。所以无法预处理，只能在枚举当前状态时看。
当我们枚举到一个状态：$dp[i][j]$的时候，我们需要知道的是$dp[i-1]$的状态。不需要考虑$dp[i+1]$的状态的原因是动态规划的无后效性。那么我们只需要再枚举$dp[i-1]$的状态，依次确认是否合法即可。合法的条件就是$k\&j=0$。也就是说，在$k$能种的地上$j$必须选择不种。
那么转移方程就是：
$$
dp[i][j]=dp[i][j]+dp[i-1][k]\quad(mod\,\,p)
$$
最终的答案还要统计所有的方案数。需要把所有状态枚举一遍，依次累加$dp[m][i]$。
那么这道题就完事了。难点不是状压的过程，是状压合法转移的判断过程。
代码：
```cpp
#include<cstdio>
#include<bitset>
using namespace std;
const int mod=1e9;
int m,n;
int map[20][20];
int dp[20][1<<12],F[20];
bool st[1<<12];
//dp[i][j]表示第i行状态为j的时候的方案数
int main()
{
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
{
scanf("%d",&map[i][j]);
F[i]=(F[i]<<1)+map[i][j];
}
for(int i=0;i<(1<<n);i++)
st[i]=((i&(i<<1))==0) && (((i&(i>>1))==0));
dp[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=0;j<(1<<n);j++)
if(st[j] && ((j&F[i])==j))
for(int k=0;k<(1<<n);k++)
if((k&j)==0)
dp[i][j]=(dp[i][j]+dp[i-1][k])%mod;
int ans=0;
for(int i=0;i<(1<<n);i++)
ans=(ans+dp[m][i])%mod;
printf("%d",ans);
return 0;
}
```