状压DP初见 洛谷 P1879 玉米田
题目描述
农场主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的余数。
输入输出样例
输入样例#1：
2 3
1 1 1
0 1 0
输出样例#1：
9
心路历程
刚学状压心情十分崩溃，尤其是看到题解里有关什么”状态j”的字眼就头疼，十分不懂= =
但是仔仔细细看看就懂了
所谓状态j其实就是用j这个数来表示一个状态，即将j转化成二进制后再读取这个数字所含信息,转化后的二进制01串中，0表示没放置，1表示放置，还是很好理解
limit就是状态上限数量，因为用二进制来表示一行x个位置的状态的话，最多也就需要x位，即数字不会超过2^x-1的大小
F数组用来表示每一行的条件，当然表现方法还是二进制= =
flag数组就是对于每个数所代表的状态合不合法的预处理，因为不能有相邻的”1″
注意位运算的级别基本上是最低的，反正有关位运算的地方全部要打括号
代码附注释
代码
#include<iostream>
#include<cstdio>
using namespace std;
int mod=1e9,limit,flag[4096],n,m,f[13][4096],F[13],ans;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
int x;
cin>>x;
F[i]=(F[i]<<1)+x;//F数组存下每一行的状态条件，F<<1左移把最后面的位置留个新的信息
}
limit=1<<m;//状态总量上限
for(int i=0;i<limit;i++)
if(((i&(i<<1))==0)&&((i&(i>>1))==0))//状态的筛选，判断i这个数字代表的状态合不合法i&(i<<1)表示每一位与左边作比较，(i>>1)则与右边，确保没有相邻，不懂的拿纸笔列一下这个if就懂了^v^
flag[i]=1;
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<limit;j++)
if(((F[i]&j)==j)&&flag[j])//flag判断对于不能相邻条件是否满足，F[i]&j的话，如果j状态满足当前行的草地限制条件，则与运算结果将会为j
for(int k=0;k<limit;k++)//如果j所代表的状态满足，从上一行的合法状态转移
if((k&j)==0)//判断是否上一行状态与此行有相邻，如果有则将有1对齐，结果将不为0
f[i][j]=(f[i][j]+f[i-1][k])%mod;//转移相加
for(int i=0;i<limit;i++)
ans=(ans+f[n][i])%mod;
cout<<ans;
}