洛谷P1879 [USACO06NOV]玉米田Corn Fields（状压DP入门题）
位运算
学习状压之前必须要熟练掌握位运算
| 位运算名 | 符号 | 效果 |
|---|---|---|
| &（and） | 按位与 | 如果两个相应的二进制位都为1，则该位的结果值为1，否则为0 |
| l（or） | 按位或 | 两个相应的二进制位中只要有一个为1，该位的结果值为1 |
| ^（xor） | 按位异或（单身狗操作） | 若参加运算的两个二进制位值相同则为0，否则为1 |
| ~ | 取反 | 一元运算符，用来对一个二进制数按位取\反，即将0变1，将1变0 |
| << | 左移 | 用来将一个数的各二进制位全部左移N位，右补0 |
| >> | 右移 | 将一个数的各二进制位右移N位，移到右端 的低位被舍弃，对于无符号数，高位补0 |
**下面是一些基本操作
题目描述
农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入输出格式
输入格式：
第一行：两个整数M和N，用空格隔开。
第2到第M+1行：每行包含N个用空格隔开的整数，描述了每块土地的状态。第i+1行描述了第i行的土地，所有整数均为0或1，是1的话，表示这块土地足够肥沃，0则表示这块土地不适合种草。
输出格式：
一个整数，即牧场分配总方案数除以100,000,000的余数
代码
#include<bits/stdc++.h>
#define mod 100000000
using namespace std;
const int M=15,N=1<<15;
int st[N],mp[M]//存可行的不相邻的状态以及图中每排的状态;
int dp[M][N];
int n,m;
int ans;
inline int read()
{
int x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
return x*f;
}
bool judge1(int x)//判断相邻两点是否冲突
{
return (x&(x<<1));
}
bool judge2(int i,int x)//判断点能不能放
{
return (mp[i]&st[x]);
}
int main()
{
n=read();m=read();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
int a=read();
if(a==0)
mp[i]+=(1<<(j-1));
/*
相当于无符号取反操作如将0 1 0变为1 0 1。
在判断能不能放做准备
*/
}
}
int k=0;
for(int i=0;i<(1<<m);i++)
{
if(!judge1(i))
st[++k]=i;
}
for(int i=1;i<=k;i++)
{
if(!judge2(1,i))
dp[1][i]=1;
}
for(int i=2;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
if(judge2(i,j))
continue;
for(int f=1;f<=k;f++)
{
if(judge2(i-1,f))continue;//剪枝
if(!(st[j]&st[f]))//判断上下是否冲突
dp[i][j]+=dp[i-1][f];
}
}
}
for(int i=1;i<=k;i++)
{
ans+=dp[n][i];
ans%=mod;
}
printf("%d",ans);
return 0;
}