嗯，作为一只蒟蒻，今天再次学习了状压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
3 2 1 0 1 -1 1 0
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 }
这样就可以了。
未完待续……
原文：https://www.cnblogs.com/xishirujin/p/10764496.html