Luogu P1879 [USACO06NOV]玉米田Corn Fields

题目

P1879 [USACO06NOV]玉米田Corn Fields

分析

状压DP入门题目。
数据规模非常小，非常适合用状压DP。

• 首先把每一行的情况压成一个二进制数，1表示选，0表示不选；
  设f[i][j]表示到计算了前i行，第i行状态为j；
• 枚举上一行所有可能的状态，按行转移；
  那么状态转移方程显然为：$f[i][j]+=f[i-1][k] \; mod \; P$
• 枚举每一行状态时需要判断，本行之内没有相邻的格子被选中，上一行与本行之间也没有相邻的格子被选中。
• 因此需要通过此行状态向左右各移一位产生的状态，与此行状态&一下，如果有某个位置是1，说明此行状态有相邻的1，则当前状态不可行,$continue$。
• 也需要用本行与上一行&一下，原理同上； 值得注意的是，只有题目输入中的1格才可能被选，所以当前的状态需要满足：
• 可以将此行当前状态与输入状态&一下，如果结果不是当前状态，说明有某一位置，当前状态为1但输入状态为0,不合法。
• 最后的答案是：枚举最后一行所有状态，只要当前状态有答案，那么必为合法状态，直接累加。

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=13,P=100000000;
int s[maxn],f[maxn][1<<maxn];
int n,m,ans;bool judge(int i,int j,int k)
{if((j&(j<<1))||(j&(j>>1)))  return false;if(j&k)                     return false;if((j&s[i])!=j)             return false;return true;
} int main()
{scanf("%d%d",&n,&m);f[0][0]=1;for(int i=1,x;i<=n;i++)for(int j=1;j<=m;j++)scanf("%d",&x),s[i]=(s[i]<<1)|x;for(int i=1;i<=n;i++)for(int j=0;j<(1<<m);j++)for(int k=0;k<(1<<m);k++)if(judge(i,j,k))f[i][j]=(f[i][j]%P+f[i-1][k]%P)%P;for(int i=0;i<(1<<m);i++)ans=(ans%P+f[n][i]%P)%P;printf("%d",ans);return 0;
}