状压DP学习笔记 - 洛谷保存站

# 一. 什么是状压DP
状压DP是一种利用位运算来高效表示和转移状态的动态规划方法。它特别适用于状态可以用二进制位表示的问题，通常处理的是"选或不选"、"存在或不存在"这类的二元状态。

## 为什么需要状态压缩？

• 常规DP在表示某些状态时需要大量空间

• 状态压缩可以极大减少内存使用

• 位运算操作非常高效，能提升算法速度(其实就是因为这个)

# 二. 常用的一些技巧（位运算）

1. **空集**
 ```cpp
int S=0;
 ```  
• 初始化一个空集合 `S`，所有二进制位均为0。

2. **将第 `i` 位置为1（加入集合）**  
 ```cpp
S|=(1<<i);  
 ```  
•将集合 `S` 的第 `i` 位设置为1（添加元素）。

3. **判断第 `i` 位是否为1**  
```cpp
S & (1 << i);  
```  
•检查集合 `S` 的第 `i` 位是否为1。若结果非0，则表示该位已设置。

4. **将第 `i` 位置为0（从集合移除）**  
```cpp
S &=~(1<<i);  
 ```  
•清除集合 `S` 的第 `i` 位（设置为0）。

5. **切换第 `i` 位的状态**  
 ```cpp
S^=(1<<i);  
 ```  
•如果第 `i` 位为0则置为1，反之则置为0（状态反转）。

6. **清除最低位的1**  
 ```cpp
S=S&(S-1);  
  ```  
•快速清除 `S` 的二进制表示中最低位的1。

# 三. 例题

## 1. [传球游戏](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=J)
没啥好说的，直接看代码注释吧
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=20;
const int M=1<<16|5;
const int inf=0x3f3f3f3f;
int n,a[N][N];
int f[M][N];
int main(){
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			scanf("%d",&a[i][j]);
	for(int s=0;s<1<<n;s++)
		for(int i=0;i<n;i++)
			f[s][i]=inf;//f[s][i]表示在s状态下球到i的最小代价  
	for(int i=0;i<n;i++)
		f[1<<i][i]=0;//可以从任意点开始，初始代价为0 
	for(int s=2;s<1<<n;s++)//遍历所有可能的状态s 
		for(int i=0;i<n;i++)//遍历所有可能的当前节点i
			if(s>>i&1)//判断s的第i位是否为1 
				for(int j=0;j<n;j++)
					if(i!=j&&(s>>j&1))//确保节点j不等于当前节点i，并且节点j也在状态s中被访问过
					//状态转移从状态s中移除节点i(s^1<<i),然后从节点j转移到节点i
                    //更新状态s下以节点i结尾的最小总代价
						f[s][i]=min(f[s][i],f[s^1<<i][j]+a[j][i]);
	int ans=inf;
	for(int i=0;i<n;i++){
		ans=min(ans,f[(1<<n)-1][i]);
		//(1<<n)-1表示全集 
	}					
	printf("%d",ans);
	return 0;
}
```

## 2. [过桥](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=K)
这题类比[护卫队](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=L)

区别：

过桥这道题**并没有要求通过的顺序**，而护卫队的输入就是通过的顺序

过桥需要用状压来解决

```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=1<<16|10;

int n,ww;
int w[N],t[N],f[N];

int main(){
    scanf("%d%d",&ww,&n);
    for(int i=0;i<n;i++){ 
        scanf("%d%d",&t[1<<i],&w[1<<i]); // 输入第i个队员的时间和重量，1<<i表示二进制第i位为1，其他为0
        f[1<<i]=t[1<<i]; // 单独过桥时，最小总时间就是该队员的时间
    }
    for(int s=1;s<1<<n;s++){ // 遍历所有可能的状态，从1到2^n-1
        if(s&s-1){ // 判断s是否不是2的幂次方，即是否包含多个队员
            // 计算状态s的时间和重量
            t[s]=max(t[s&s-1],t[s&-s]); // s&-s得到s的最低位的1，s&s-1是去掉最低位的1后的状态
            w[s]=w[s&s-1]+w[s&-s]; // 同样，计算总重量
            if(w[s]<=ww){ // 如果当前状态的重量不超过桥的最大承重
                f[s]=t[s]; // 那么当前状态的最小总时间就是该组的最长时间
            }
            else{ // 如果超重，则需要将该状态拆分成多个子状态
                f[s]=0x3f3f3f3f; // 初始化为一个很大的值
                for(int tt=s-1&s;tt;tt=tt-1&s){ // 枚举s的所有非空子集tt
                    if(w[tt]<=ww && f[s]>f[s^tt]+t[tt]){ // 如果子集tt不超重，并且可以更新f[s]
                        f[s]=f[s^tt]+t[tt]; // 更新f[s]为子集tt的时间加上剩余部分的时间
                    }
                }
            }
        }
    }
    printf("%d",f[(1<<n)-1]); // 输出所有队员都过桥后的最小总时间
    return 0;
}
```
## 3. [校长的烦恼](http://oi.nks.edu.cn:19360/zh/Problem/Details?cid=3311&tid=M)
```cpp
#include<bits/stdc++.h>
using namespace std;

int s,m,n;
int f[300][300]; // 动态规划数组，f[i][j] 表示达到该状态的最小工资
int money[150],w[150];
int s1,s2,ans; // s1: 当前至少有一名教师的课程掩码; s2: 当前至少有两名教师的课程掩码; ans: 初始总工资（在职教师的工资总和）

int main(){
    scanf("%d%d%d",&s,&m,&n);
    int ss=(1<<s)-1; 
    for(int i=1;i<=m;i++){
        int sal;
        scanf("%d",&sal);
        ans+=sal;
        string x;
        getline(cin,x);
        for(int j=0;j<x.size(); j++){
            if(x[j]!=' '){ 
                int t =x[j]-'0';
                s2=s2|(s1&(1<<(t-1)));// 更新至少有两名教师的集合 
                s1=s1|(1<<(t-1));//更新至少有一名教师的集合
            }
        }
    }
    memset(f,0x3f,sizeof f);
    f[s1][s2]=ans;//在职教师的状态和总工资
    for(int i=1;i<=n;i++){
        scanf("%d",&money[i]);
        string x;
        getline(cin,x);
        for(int j=0;j<x.size();j++){
            if(x[j]!=' '){
                int t=x[j]-'0';
                w[i]=w[i]|(1<<(t-1));
            }
        }
    }
    for(int i=1;i<=n;i++){// 遍历每个求职者
        for(int j=ss;j>=0;j--){//遍历所有可能的s1状态
            for(int k=ss;k>=0;k--){//遍历所有可能的s2状态
                int s11=j|w[i];
                int s22=k|(j&w[i]);
                f[s11][s22]=min(f[s11][s22],f[j][k]+money[i]); // 更新最小工资
            }
        }
    }

printf("%d", f[ss][ss]); // 输出所有课程都有至少两名教师的最小总工资
    return 0;
}
```
注意：
```cpp
s2=s2|(s1&(1<<(t-1))); 
s1=s1|(1<<(t-1));
```
更新s1与s2时，因为s2是由上一次得到的s1更新的，所以要先更新s2，再更新s1

# End.

正在渲染内容...