本篇文章将从状态压缩入门开始讲起。
什么是状态压缩
假设你面前有 \(n\) 盏灯，每盏灯的状态有：开、关。如何表示这个状态呢？
简单，用个 bool 数组，搞定！
那，如果 \(n\) 非常大，大到数组开不下怎么办呢？
其实很简单，我们把开的状态记为 \(1\)，关着的状态记为 \(0\)。那么这一串灯就可以用 \(1\) 和 \(0\) 的二进制表示。再转换成 \(10\) 十进制就可以了。比如十个灯，状态分别为：开关开开关开开关关关，那么就可以表示为 \((1011011000)_2=(728)_{10}\)。
这就是状态压缩。十分简单。
然后我们再在其基础上进行 DP 就是所谓的状压 DP 了！
因为涉及到二进制位枚举，所以数据范围一般都在 \(20\) 左右，因为 \(2^{20}\approx 10^6\)，差不多就是最大值了。
例题
A：P2622 关灯问题 II
这个题目和我们上面举的例子非常像，所以很容易看出把灯状态压缩。接下来就有两种做法。
做法一
一开始的状态为 \((111\dots 1)_2\)，有 \(n\) 个 \(1\)。换成十进制就是 \(2^{n+1}-1\)。我们的目标是 \((000\dots 0)_2=(0)_{10}\)，考虑搜索能否到达。用 BFS 搜索，然后就是板子了。时间复杂度 \(O(nm\cdot 2^n)\)。
code:
/*
------- INFO -------
> Date:2025/12/27
> Time:09:20:03
> Filename:P2622.cpp
> Path:~/桌面/dhx/P2622.cpp
--------------------
*/
#include <iostream>
#include <queue>
#include <cstdio>
#define int long long
#define endl '\n'
using namespace std;int n,m;
int a[105][15];
bool vis[1<<11];
struct node{int x;//now statusint s;//step
};
void bfs(){queue<node> q;q.push({(1<<n)-1,0});vis[(1<<n)-1] = true;while(!q.empty()){node f = q.front();q.pop();for(int i = 1;i<=m;i++){int now = f.x;for(int j = 1;j<=n;j++){//枚举使用哪个按钮并修改if(a[i][j]==1){now = (now&(~(1<<(j-1))));}if(a[i][j]==-1){now = (now|((1<<(j-1))));}}if(vis[now]) continue;//如果访问过就不再访问vis[now] = true;// cout<<now<<endl;if(now==0){//如果是0，立即退出cout<<f.s+1;exit(0);}q.push({now,f.s+1});}}
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>m;for(int i = 1;i<=m;i++){for(int j = 1;j<=n;j++){cin>>a[i][j];}}bfs();cout<<-1;//否则如果到最后都没有退出，得到结论：无解return 0;
}