状压dp学习笔记（持续更新）
嗯，作为一只蒟蒻，今天再次学习了状压dp（学习借鉴的博客）
但是，依旧懵逼··································
这篇学习笔记是我个人对于状压dp的理解，如果有什么不对的地方，希望大家指出。
闲话不多说，进入正题。
首先，在介绍状压dp之前，我们先来了解一下状态压缩（常用的为二进制，why？【因为其他的我不会】）。
什么是状态压缩呢？顾名思义，就是将数转换为二进制来进行一些操作。
基本操作：
看完基本操作，我们来看一下一些稍微复杂的操作。
| 操作 | 运算 |
| 取出整数n在二进制表示下的第k位 | （n>>k）&1 |
| 取出整数n在二进制表示下的第0~k-1位（后k位） |
n&((1<<k)-1) |
| 取出整数n在二进制表示下的第k位取反 | n^(1<<k) |
| 取出整数n在二进制表示下的第k位赋值为1 | n|(1<<k) |
| 取出整数n在二进制表示下的第k位赋值为0 | n&(~(1<<k)) |
大概就是这些了，如果有看不懂的地方大家可以手推一下。
下面我们来看一道状态压缩的题
题目描述
现有n盏灯，以及m个按钮。每个按钮可以同时控制这n盏灯——按下了第i个按钮，对于所有的灯都有一个效果。按下i按钮对于第j盏灯，是下面3中效果之一：如果a[i][j]为1，那么当这盏灯开了的时候，把它关上，否则不管；如果为-1的话，如果这盏灯是关的，那么把它打开，否则也不管；如果是0，无论这灯是否开，都不管。
现在这些灯都是开的，给出所有开关对所有灯的控制效果，求问最少要按几下按钮才能全部关掉。
输入输出格式
输入格式：前两行两个数，n m
接下来m行，每行n个数,a[i][j]表示第i个开关对第j个灯的效果。
输出格式：一个整数，表示最少按按钮次数。如果没有任何办法使其全部关闭，输出-1
输入输出样例
输入样例#1：3 2 1 0 1 -1 1 0输出样例#1：
2
说明
对于20%数据，输出无解可以得分。
对于20%数据，n<=5
对于20%数据，m<=20
上面的数据点可能会重叠。
对于100%数据 n<=10,m<=100
题目分析：
这时候，如果我们在考试的时候实在没有思路的话就……输出-1吧！
好了，不闹了，回归正题。看到这个题的时候我们会想到搜索，这并非不是一个可能的解法。
再看一下题目结构，只有开和关的两种状态，所以我们就可以用0和1来表示，此时我们就可以用二进制来表示。
开——1，关——0
接下来，我们就要进行搜索了。
由于在初始时我们得到的状态全部都是开的，所以我们就需要n个1，这时我们就用 int num=(1<<(n))-1; 来表示n个1。
然后我们在搜索时去寻找开关为1/-1的状态，并在找到时进行判断和步数的统计，最后判断是否将所有状态全部改正即可。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 template<typename type> 4 void scan(type &x){ 5 type f=1;x=0;char s=getchar(); 6 while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();} 7 while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();} 8 x*=f; 9 } 10 const int maxn=2007; 11 struct node{ 12 int step,zt; 13 }; 14 int vis[maxn],mp[maxn][maxn]; 15 int n,m; 16 17 void bfs(int num){ 18 queue<node>q; 19 node f;f.step=0;f.zt=num;//初始状态 20 q.push(f);//入队 21 while(!q.empty()){ 22 node u=q.front(); 23 q.pop(); 24 int pre=u.zt; 25 for(int i=1;i<=m;i++){//枚举 26 int now=pre; 27 for(int j=1;j<=n;j++){ 28 if(mp[i][j]==1){ 29 if((1<<(j-1))&now){//如果第j位的开关为1，且当前的灯还开着， 30 now=now^(1<<(j-1));// 这时候将其状态修改 31 }} 32 else{ 33 34 if(mp[i][j]==-1){//如果第j位的开关为-1，且当前的灯关着， 35 now=((1<<(j-1))|now);// 这时候将其状态修改 36 } 37 } 38 } 39 f.zt=now;f.step=u.step+1; 40 if(vis[now]==1)continue;//打标记，防止重复 41 if(f.zt==0){ 42 vis[0]=1;//标记 43 printf("%d\n",f.step); 44 return ; 45 } 46 q.push(f);//入队 47 vis[now]=1; //标记 48 } 49 50 } 51 } 52 53 int main(){ 54 scan(n);scan(m); 55 int num=(1<<(n))-1;//找到n位1 56 for(int i=1;i<=m;i++){ 57 for(int j=1;j<=n;j++){ 58 scan(mp[i][j]); 59 } 60 } 61 bfs(num); 62 if(vis[0]==0){ 63 printf("-1\n"); 64 } 65 return 0; 66 }
这样就可以了。
下面，我们来介绍一道十分基础的状压dp的题目
题目描述
Farmer John has purchased a lush new rectangular pasture composed of M by N (1 ≤ M ≤ 12; 1 ≤ N ≤ 12) square parcels. He wants to grow some yummy corn for the cows on a number of squares. Regrettably, some of the squares are infertile and can't be planted. Canny FJ knows that the cows dislike eating close to each other, so when choosing which squares to plant, he avoids choosing squares that are adjacent; no two chosen squares share an edge. He has not yet made the final choice as to which squares to plant.
Being a very open-minded man, Farmer John wants to consider all possible options for how to choose the squares for planting. He is so open-minded that he considers choosing no squares as a valid option! Please help Farmer John determine the number of ways he can choose the squares to plant.
农场主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
未完待续……
