状态压缩
适用范围
维数很多+总量很少时，可以将状态压缩为一个数来记录 【一般就是有n<20,n<12这种很小的范围的时候，要考虑到状态压缩】 参考：https://www.cnblogs.com/shzr/p/9064737.html
状态压缩就是把很多维度的状态，压缩成一个数值来表示。比如用二进制/十进制等的方式来存储状态，把状态变成一个数字。
例如：vis[x]=1，表示访问过这个状态x。
通过化状态为数组【把多维度降为1维】，可以对这个状态进行dp、bfs、dfs搜索等
状态压缩DP
1.玉米田 洛谷P1879
①题目描述
农场主John新买了一块长方形的新牧场，这块牧场被划分成M行N列(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)，每一格都是一块正方形的土地。John打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。
遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是John不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。
John想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
链接：https://www.luogu.org/problemnew/show/P1879
②解题思路
对于很多小图【小棋盘等】的搜索都是用可以用状态压缩来做的。把整个例如3*3的棋盘状态用那个9位十进制数/二进制数来存储。
类似地，这里有：(1 ≤ M ≤ 12; 1 ≤ N ≤ 12)。
很显然，这是总范围小，但是维度大的情况。要考虑状态压缩。
但是12*12=144来表示一个状态显然太大了，不论是二进制还是几进制。
因此要考虑行转移，把一行作为一个状态，进行行压缩。
状态转移方程
以一个二进制数表示一个行状态，1表示种了草，0表示没有。
dp[i][j] 表示考虑前i行，第i行状态为j时可行的总方案数。
因此状态转移方程为：
dp[i][j]=∑dp[i−1][k]【其中j,k两状态都合法】
可以理解为：前i-1行中的所有合法状态【遍历k】的方案和等于在第i行放置合法状态j【j和k状态位于第i行和第i-1行可相容，即无相邻草地】可达到的前i行可行方案总数。
则最后ans=∑dp[n][j] 【其中 j遍历每个状态，即0<=j<=(1<<m)−1且j合法】
空间优化：合法状态j->第j个合法状态
考虑到状态转移的时候每次都要枚举2^m个状态【每行有m个列】 其中有些状态本身就不合法（即相邻位置种了草），这样会造成无用枚举 所以可以一开始先预处理出只考虑不相邻的所有合法方案，大大减少枚举量。
这样dp[i][j]中的一维维度就会下降。本来j位置应该开辟2^m大小的空间。
如果我们做一个预处理，把dp[i][j]重新定义为第j个合法状态【而不是合法状态j】，就可以大幅减少空间消耗。【将具体状态存储到一个新的数组中（rem[j]），用j索引到具体状态】
如果2^m中，抛除相邻位置种了草的方案，剩下的合法状态会大大减少为k，那么dp[i][j]中j位置只需要k大小的空间。
合法性判断
（1）行内相邻：关于状态x是否合法的判断
//状态x表示某行的状态，二进制位为1表示种了草
if( (( x&(x<<1) )==0) && (( x&(x>>1) )==0) )
return true;
else
return false;
即将x分别左移和右移，若x二进制中某相邻两位皆为1，则左/右移后两位重合，&运算必定返回1,表示不合法。
必须最多是……010101……交替，再移动一位以后才使得x&(x«1)=0
（2）土地是否可种：判断状态x是否与土地情况冲突
在读入时记录st[i]，表示第i行的土地情况，具体每个位，用1表示能种，0表示不能种。那么：
if((~st[i])&rem[i]) return 0
将st每位取反，那么则1表示不能种，&运算后返回不等于0，说明状态x一定在不合法的位置种了草【有某个已种草位和贫瘠土地都为1，&之后返回非0】。
（3）列内相邻
//rem[j]为第i行的状态，rem[k]为第i-1的行的状态
if(rem[k]&rem[j]!=0)//上下相邻，列内相邻。
continue;
复杂度
dp[i][j]=∑dp[i−1][k]【其中j,k两状态都合法】
复杂度：O(2^(2∗m)∗n)
其中，两个带2的次方的是当前行的合法状态枚举和上一行的合法状态枚举=（2^m）*（2^m）=2^(m+m)=2^(2∗m)，n是行数【往外层从i-1推出i】
③解题代码
#include<iostream>
#include<vector>
#include<string.h>
#define MOD 100000000
using namespace std;
int st[15];
int rem[3100];//2^12=1024*4,优化后的合法数大概3100
int cnt;//可以试着打一下表，看看cnt的值，来估计合法数
int n,m;
int dp[15][3100];
bool check(){
cnt=0;
for(int x=0;x<=(1<<m)-1;x++){
if((x&(x<<1))!=0)
continue;
if((x&(x>>1))!=0)
continue;
rem[cnt++]=x;
}
}
int main(){
cin>>n>>m;
memset(st,0,sizeof(st));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
int temp;
cin>>temp;
st[i]=st[i]|(temp<<j);
}
}
check();
//cout<<cnt<<endl;
//dp初始化
for(int i=0;i<cnt;i++){
if((~st[0])&rem[i])
continue;
dp[0][i]=1;
}
for(int i=1;i<n;i++){
for(int j=0;j<cnt;j++){
if((~st[i])&rem[j])
continue;
//在第i行为第j个合法状态时，前i-1行的、与j状态相容的、合法方案全部相加
//得到第i行为第j个合法状态时，前i行的合法方案总数。
//当然第i行可以有多个合法状态。
for(int k=0;k<cnt;k++){
//注意!=和==的优先级比&高，因此运算要加括号
if((rem[k]&rem[j])!=0)//上下相邻，列内相邻。
continue;
if((~st[i-1])&rem[k])
continue;
dp[i][j]=(dp[i][j]+dp[i-1][k])%MOD;
}
}
}
int ans=0;
for(int i=0;i<cnt;i++){
ans=(ans+dp[n-1][i])%MOD;
}
cout<<ans<<endl;
return 0;
}
