Luogu P1879 [USACO06NOV]Corn Fields G 题解
Describe
题目链接
给一个Mtimes N的矩阵，矩阵每个位置为0/1，问选一些1使这些不相邻的方案数。
Solution
明显状压DP。
那么怎么DP呢？
设f[i][j]表示第i行状态为j的方案数。
那么转移就可以暴力枚举上一行的状态再判断可能性转移。
那么怎么判断是否可行呢？
!j&(j<<1)&&!j&(j>>1)
直观感受
那么还有什么条件呢？S[i]&jtext{^}j1。!j&k
那么就直接上代码（逃：
Code
代码语言：javascript复制#include<bits/stdc .h>
#define mod 100000000
using namespace std;
int m,n,S[20],f[20][(1<<13) 10],ans;
int main(){
cin>>m>>n;
for(int i=1;i<=m;i )
for(int x,j=1;j<=n;j )
cin>>x,S[i]=S[i]<<1x;//整合一行信息
f[0][0]=1;//初始化
for(int i=1;i<=m;i ){
for(int j=0;j<(1<<n);j ){
if(j&(j<<1)j&(j>>1)S[i]&j^j) continue ;//判断三个条件
for(int k=0;k<(1<<n);k ){
if(k&j) continue ;//和上一行有冲突
f[i][j] =f[i-1][k];//累计
f[i][j]%=mod;
}
}
}
for(int i=0;i<(1<<n);i ) ans =f[m][i],ans%=mod;//总和
cout<<ans<<endl;
} 
