状压DP

0.前言

位运算记不记得？
(n>>k)&1 取出非负数n的第k位
n&((1<<K)-1) 取出非负数n的后k位
n^(1<<k)把非负数n的第k位取反
n^(1<<k)把非负数的第k位取反

1.定义与例题引入

状压 DP 是动态规划的一种，通过将状态压缩为整数来达到优化转移的目的。 ——oiwiki

那么怎么个状态压缩法呢？

例如这个题： P1896 [SCOI2005] 互不侵犯

在$N \times N$ 的棋盘里面放$K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共$8$ 个格子。($1\le N \le 9,0\le K \le N\times N$)

这里我们发现好像我们可以设几个状态，分别是放到第几行，放了多少个国王，和如何放置的。前两个都好说，但是第三个却让我们很头疼。如果按照常规思路来想，我们肯定会开一个非常非常大的数组来表示这个放置状态，而且甚至移动方向是8个方向，更头疼，怎么办？

状态压缩就是来干这种事的，我们可以用一个二进制数来表示国王放置的状态。设一个二进制数，当它的一个数位表示1的时候就表明放置的国王，如果表示0就表示没有放置国王，如下图。

这样的话我们只需要一个十进制整数就可以对应唯一一个放置国王的状态，也就不需要开那么多的空间啦。

但是对于一个状态来说，有可能合法，也有可能并不合法，并且在判断的时候我们还要处理出攻击范围以及放置了多少个国王，很麻烦。。。。？

我们可以预处理啊！

cin>>n>>k;
int tt=1<<n;
for(int i=0;i<tt;i++){//i的二进制位表示一列上国王的摆放状态
    isok[i]=((i&(i<<1))==0)&&((i&(i>>1))==0);//状态是否合法
    attack[i]=i|(i<<1)|(i>>1);//攻击范围
    cnt1[i]=cnt1[i>>1]+(i&1);//总共多少个1（国王数量）
}

接下来我们来看$isok$这个数组怎么判断的，还是上面那个图，我们对i & (i<<1)做一下解释。

如果有非法的情况呢？

右移同理。

那么$attack$攻击范围如何处理呢，如下图：

对于1的统计$cnt$，这个就不多说了自己画图吧（逃

那么开始dp，其实之前已经说出来转移方程了，这一贴一个oiwiki的

故有代码如下：

f[0][0][0]=1;
for(int i=0;i<n;i++){//枚举行数
    for(int j=0;j<tt;j++){//枚举状态
        for(int l=0;l<=k;l++){//枚举放多少个国王
            if(f[i][j][l]){//如果当前位置有放置的话
                for(int p=0;p<tt;p++){
                    if(isok[p]&&(attack[p]&j)==0){
                        //如果状态合法并且攻击范围不在j的状态表示内
                        f[i+1][p][l+cnt1[p]]+=f[i][j][l];
                        //对下一行执行操作累加答案
                    }
                }
            }
        }
    }
}

让后拼装以下，就有了AC代码

#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int MN=(1<<10)+15;
int isok[MN],attack[MN],cnt1[MN],n,k;
ll ans,f[121][MN][121];
int main(){
    cin>>n>>k;
    int tt=1<<n;
    for(int i=0;i<tt;i++){//i的二进制位表示一列上国王的摆放状态
        isok[i]=((i&(i<<1))==0)&&((i&(i>>1))==0);//状态是否合法
        attack[i]=i|(i<<1)|(i>>1);//攻击范围
        cnt1[i]=cnt1[i>>1]+(i&1);//总共多少个1（国王数量）
    }
    f[0][0][0]=1;
    for(int i=0;i<n;i++){//枚举行数
        for(int j=0;j<tt;j++){//枚举状态
            for(int l=0;l<=k;l++){//枚举放多少个国王
                if(f[i][j][l]){//如果当前位置有放置的话
                    for(int p=0;p<tt;p++){
                        if(isok[p]&&(attack[p]&j)==0){
                            //如果状态合法并且攻击范围不在j的状态表示内
                            f[i+1][p][l+cnt1[p]]+=f[i][j][l];
                            //对下一行执行操作累加答案
                        }
                    }
                }
            }
        }
    }
    for(int i=0;i<tt;i++){
        ans+=f[n][i][k];
    }
    cout<<ans;
    return 0;
}

当然最后统计答案的时候需要一个一个枚举状态。

例题1: P1879 [USACO06NOV] Corn Fields G

农场主$\rm John$ 新买了一块长方形的新牧场，这块牧场被划分成$M$ 行$N$ 列$(1 \le M \le 12, 1 \le N \le 12)$，每一格都是一块正方形的土地。$\rm John$ 打算在牧场上的某几格里种上美味的草，供他的奶牛们享用。

遗憾的是，有些土地相当贫瘠，不能用来种草。并且，奶牛们喜欢独占一块草地的感觉，于是$\rm John$ 不会选择两块相邻的土地，也就是说，没有哪两块草地有公共边。

$\rm John$ 想知道，如果不考虑草地的总块数，那么，一共有多少种种植方案可供他选择？（当然，把新牧场完全荒废也是一种方案）
输入样例将给出每一格的贫瘠和肥沃的状态

根据上面的思想，我们可以很容易设计出来状态转移方程。

设$f[i][j]$表示前$i$行已经种完，开始种第$i$行，按照$j$的状态进行种植能获得的方案

故有$f[i][j]=f[i][j]+f[i-1][k]$，其中$k$是枚举上一行的的种植状态

我们显然可以知道，对于种植状态，判断条件有2个，第一个是该土地是否肥沃（能否种植），第二个是种植时不能出现相邻，如下，橙色为种植点，红色为不能种植点。

对于该一行的种植很简单，和之前一样照常写$isok$就可以了，但是竖直方向怎么
处理？很简单我们发现如果有覆盖种植的话那么与起来一定会出现一个大于0的数，没有那么一定为0。

放码过来吧！
注意这里的isok写法不同

#include<iostream>
using namespace std;
const int MN=15,MK=1<<MN,MOD=1e8;
int n,m,map[MN][MN],st[MK],isok[MK],f[MN][MK],ml;
int main(){
    cin>>n>>m;
    ml=(1<<m);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>map[i][j];
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            st[i]=(st[i]<<1)+map[i][j];
        }
    }
    for(int i=0;i<ml;i++){
        isok[i]=((i&(i<<1))==0);
    }
    f[0][0]=1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<ml;j++){
            if(isok[j]&&((j&st[i])==j)){
                for(int k=0;k<ml;k++){
                    if(!(j&k)){
                        f[i][j]=(f[i][j]+f[i-1][k])%MOD;
                    }
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<ml;i++){
        ans=(ans+f[n][i])%MOD;
    }
    cout<<ans;
    return 0;
}

例题2: P10963 Islands and Bridges

给定一张由岛屿和连接这些岛屿的桥梁构成的地图，众所周知，哈密顿路径是沿着桥梁的路径，能够恰好访问每个岛屿一次。在我们的地图中，每个岛屿还关联一个正整数值。我们定义一种哈密顿路径为 最佳三角形哈密顿路径，其最大化以下描述的值。

假设有$n$ 个岛屿。哈密顿路径$C_1,C_2,\dots,C_n$ 的值分为三部分计算。设$V_i$ 为岛屿$C_i$ 的值。第一部分为路径中每个岛屿的$V_i$ 值的总和。第二部分，对于路径中的每条边$C_i C_{i+1}$，加上$V_i \times V_{i+1}$ 的积。第三部分，对于路径中的每三个连续岛屿$C_i, C_{i+1}, C_{i+2}$，如果它们在地图中形成一个三角形（即$C_i$ 和$C_{i+2}$ 之间有桥），加上$V_i \times V_{i+1} \times V_{i+2}$ 的积。

最佳三角形哈密顿路径很可能（但不一定）包含多个三角形。可能会存在多个最佳三角形哈密顿路径。你的第二个任务是找出这样的路径的数量。

对于三角形路径，在DP中如果考虑枚举端点拼凑，那么时间复杂度是不可承受的，我们可以直接在状态中加上2个点，枚举第3个点即可。

那就设$f_{i,j,S}$表示枚举2个点$i,j$，之前加入点的集合为$S$。用邻接矩阵存图判断起来好一点…
这里邻接矩阵设为$mp$

转移方程也很简单，枚举3个点，就有：

$$f_{i,j,s}=\max\limits_{mp[i][j]=1,mp[j][k]=1}f_{j,k,S\oplus 2^{i-1}}+V_i+V_i \times V_j+\begin{cases} V_{i}\times V_{j} \times V_{k} & mp[i][k]=1 \\ 0 & mp[i][k]=0 \end{cases}$$

路径数怎么统计，如果用pre数组记录直接爆炸，那么直接考虑dp数量，设$g_{i,j,S}$，字母含义见上，有：

$$g_{i,j,S}=\begin{cases} g_{j,k,S\oplus2^{i-1}} & f_{i,j,S}<f_{j,k,S\oplus2^{i-1}}+t \\ g_{j,k,S\oplus2^{i-1}}+g_{i,j,S} & f_{i,j,S} = f_{j,k,S\oplus2^{i-1}}+t \\ g_{i,j,S} & f_{i,j,S}>f_{j,k,S\oplus2^{i-1}}+t \end{cases}$$

故有代码如下：

#include<bits/stdc++.h>
#define int long long  // 定义 int 为 long long 类型，避免溢出
using namespace std;

const int MN = 14;  // 最大岛屿数量
int T;  // 测试用例的数量
int f[MN][MN][1 << MN], g[MN][MN][1 << MN], v[MN], n, m;  // DP 数组、岛屿值、岛屿数量、桥梁数量
bool mp[MN][MN];  // 邻接矩阵，表示岛屿之间是否有桥梁

void solve() {
    // 初始化变量
    memset(v, 0, sizeof(v));  // 初始化岛屿值数组
    memset(f, 0, sizeof(f));  // 初始化 DP 值数组
    memset(g, 0, sizeof(g));  // 初始化 DP 计数数组
    memset(mp, 0, sizeof(mp));  // 初始化邻接矩阵

    cin >> n >> m;  // 输入岛屿数量和桥梁数量
    for (int i = 1; i <= n; i++) {
        cin >> v[i];  // 输入每个岛屿的值
    }

    // 输入桥梁信息并构建邻接矩阵
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        mp[u][v] = mp[v][u] = 1;  // 标记双向桥梁
    }

    // 特殊情况处理：只有一个岛屿
    if (n == 1) {
        cout << v[1] << " " << 1 << '\n';  // 输出该岛屿的值和路径数量
        return;
    }

    // 初始化 DP 数组：处理长度为 2 的路径
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j || !mp[i][j]) continue;  // 跳过相同岛屿或没有桥梁的情况
            f[i][j][(1 << (i - 1)) | (1 << (j - 1))] = v[i] * v[j] + v[i] + v[j];  // 计算路径值
            g[i][j][(1 << (i - 1)) | (1 << (j - 1))] = 1;  // 初始化路径数量
        }
    }

    // DP 状态转移：处理更长的路径
    for (int i = 0; i < 1 << n; i++) {  // 遍历所有状态
        for (int j = 1; j <= n; j++) {  // 遍历所有可能的当前岛屿
            if (!((i >> (j - 1)) & 1)) continue;  // 跳过未访问的岛屿
            for (int k = 1; k <= n; k++) {  // 遍历所有可能的上一个岛屿
                if (j == k || !mp[j][k] || !((i >> (k - 1)) & 1)) continue;  // 跳过无效情况
                for (int p = 1; p <= n; p++) {  // 遍历所有可能的下一个岛屿
                    if (!((i >> (p - 1)) & 1) || j == p || k == p || !mp[k][p] || !g[k][p][i ^ (1 << (j - 1))]) continue;  // 跳过无效情况
                    int val = f[k][p][i ^ (1 << (j - 1))] + v[j] + v[j] * v[k] + (mp[j][p]) * v[j] * v[k] * v[p];  // 计算新路径值
                    if (val == f[j][k][i]) g[j][k][i] += g[k][p][i ^ (1 << (j - 1))];  // 更新路径数量
                    else if (val > f[j][k][i]) {  // 如果新路径值更大
                        f[j][k][i] = val;  // 更新最大路径值
                        g[j][k][i] = g[k][p][i ^ (1 << (j - 1))];  // 更新路径数量
                    }
                }
            }
        }
    }

    // 计算最终结果
    int ans = 0, cnt = 0;  // 最大路径值和路径数量
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (!mp[i][j] || !g[i][j][(1 << n) - 1] || i == j) continue;  // 跳过无效情况
            if (ans < f[i][j][(1 << n) - 1]) {  // 如果找到更大的路径值
                ans = f[i][j][(1 << n) - 1];  // 更新最大路径值
                cnt = g[i][j][(1 << n) - 1];  // 更新路径数量
            } else if (ans == f[i][j][(1 << n) - 1]) {  // 如果路径值相同
                cnt += g[i][j][(1 << n) - 1];  // 累加路径数量
            }
        }
    }

    // 输出结果，路径数量除以 2 是因为路径的顺序反转被视为相同的路径
    cout << ans << " " << (cnt >> 1) << '\n';
}

signed main() {
    cin >> T;  // 输入测试用例数量
    while (T--) {
        solve();  // 处理每个测试用例
    }
    return 0;
}

2.状压DP的另一种状压——枚举子集

例题如下：P5911 [POI 2004] PRZ

有$n$个人需要过桥，第$i$的人的重量为$w_i$，过桥用时为$t_i$这些人过桥时会分成若干组，只有在某一组的所有人全部过桥后，其余的组才能过桥。桥最大承重为$W$，问这些人全部过桥的最短时间。
$100\le W \le400$ ，$1\le n\le 16$，$1\le t\le50$，$10\le w\le100$。

数据范围较小，可以进行状压，我们发现这题的关键就是分组别的规划。故我们可以设状态$f[i]$，表示状态为$i$下过桥最少要用的时间。

状态$i$表示把每个人选或不选压为二进制。

故有$f[i]=min\{ f[j]+mt[i\,xor\,j]\}$

其中$i\,xor\,j$表示$i$种除$j$外剩余的子集，前提$j$是$i$的子集

但是我们对于每个状态要统计他们的最大重量和和时间，每个状态都是二进制数，怎么分别取出有没有人在其中呢？

这就是这章要讲的——枚举子集。

怎么枚举？先看代码。

int ml=1<<n;
    for(int i=0;i<ml;i++){
        for(int j=i;;j=(j-1)&i){
	        // j是i的一个非空子集
		    // ...
        }
    }

我怎么证明这个是对的呢？
我们枚举一下，看下图。

详细证明如下：

遍历子集的时间复杂度是$O(3^n)$

故我们可以得到转移代码如下：

for(int i=0;i<ml;i++){
    for(int j=i;;j=(j-1)&i){
        if(mw[i^j]<=w){
            f[i]=min(f[i],f[j]+mt[i^j]);
        }
        if(!j) break;
    }
}

拼装一下，AC代码如下

#include<iostream>
#include<cstring>
using namespace std;
const int MN=450,MF=(1<<16)+15;
int w,n;
int t[MN],wei[MN],ml,f[MF],mt[MF],mw[MF];
int main(){
    cin>>w>>n;
    ml=(1<<n);
    for(int i=1;i<=n;i++){
        cin>>t[i]>>wei[i];
    }
    for(int i=0;i<ml;i++){
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1))){
                mt[i]=max(mt[i],t[j]);
                mw[i]+=wei[j];
            }
        }
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=0;i<ml;i++){
        for(int j=i;;j=(j-1)&i){
            if(mw[i^j]<=w){
                f[i]=min(f[i],f[j]+mt[i^j]);
            }
            if(!j) break;
        }
    }
    cout<<f[ml-1];
    return 0;
}

3.状压DP的拓展，三进制优化+DFS（例题引入）

来看题

P7689

给定$N \times M$的矩形，让你在上面放尽量多的$2\times 3$的矩形（或$3\times 2$，就是横着竖着都可以放），矩形上有一些坏点，放置的矩形不能覆盖这些坏点，求最多能放多少个矩形。

多组测试数据，$1\le T\le 5,1\le N \le 150,1\le M \le 10$
内存限制：8MB;时间限制：2s

我们不难可以用类似P1879或炮兵阵地类似的思想，也就是平面覆盖问题。但是这里出现一个问题，这里的宽是2或3！如果单纯用二进制枚举的话转移方程会十分甚至九分的复杂，而且状态还不好表示。

那我们就可以使用三进制，三进制的一个好处就是数字拓展到$0,1,2$，那么对于这个题来说，我们使用三进制枚举，按行自上往下递推。

那么就是以下2个合法状态：

我们从右往左按列枚举当前行，记当前位置为$pos$，分2种情况：

1. 如果枚举到$pos$位，如果上一行对应的不是0，那么我们就要根据上图，填写相应的数，就是$2\rightarrow 1,1\rightarrow 0$。如果当前位置是坏的无法填写，那么排除。
2. 如果是0，那么我们3种情况
   • 填0直接跳过
   • 填1，前提是右边3个都能够填写上1，这里判断方法其实和上面是一样的。
   • 填2，右边2个要都能填写上2，同上

但是这么麻烦的情况，转移方程真的不太好得出。

没关系，DP2种实现方式，一种叫迭代，另一种叫记忆化搜索。

这里我们定义$f[i][j]$表示第$i$行填写的状态为$j$($j$为三进制数)

那么就可以从$i-1$转移过来，但是这里的内存限制是8MB，没关系滚一滚就好了。

#include<bits/stdc++.h>
using namespace std;

// 定义常量与全局变量
constexpr int MN=16; // 最大列数（题目中M≤10，此处设为16足够）
constexpr int NINF=-1061109567; // 极大负数，用于初始化DP数组
int T,n,m,k; // 测试用例数，硅片的行数，列数，坏块数量
int f[2][1<<MN]; // DP数组，滚动数组存储前两行状态，2表示滚动，1<<MN是三进制状态数上限
int pw[MN]; // 3的幂次数组，用于三进制位运算
bool isbad[MN][MN]; // 标记硅片中坏块的位置

// 获取三进制数的第pos位数值（0/1/2）
int getn(int x,int pos){
    return x%pw[pos]/pw[pos-1];
}

// 判断当前位置是否可以放置芯片
bool isok(int x,int lst,int pos){
    // 当前位置非坏块，且上一行对应位置为0
    if(!isbad[x][pos]&&!getn(lst,m-pos+1)) return 1;
    return 0;
}

// 深度优先搜索生成当前行的合法状态并更新DP值
void dfs(int x,int lst,int now,int pos,int cnt){
    if(!pos){ // 所有列处理完毕
        // 更新当前行now状态的最大芯片数：前一行lst的值 + 当前cnt
        f[x%2][now] = max(f[x%2][now], f[(x-1)%2][lst] + cnt);
        return;
    }
    // 处理上一行当前列非0的情况（受约束）
    if(getn(lst,pos)){
        // 当前列损坏则无法放置
        if(isbad[x][m-pos+1]) return;
        // 根据上一列的值决定当前列只能为1或0
        if(getn(lst,pos)==2) dfs(x,lst,now*3+1,pos-1,cnt); // 上一列是2 → 当前列必须为1
        else dfs(x,lst,now*3,pos-1,cnt); // 上一列是1 → 当前列必须为0
    }else{
        // 不放置任何芯片，直接跳过
        dfs(x,lst,now*3,pos-1,cnt);
        // 尝试放置3×2竖直芯片（需要连续两列）
        if(pos>=2 && 
           isok(x,lst,m-pos+1) && 
           isok(x,lst,m-pos+2)){
            dfs(x,lst,(now*3+2)*3+2,pos-2,cnt+1);
        }
        // 尝试放置2×3水平芯片（需要连续三列）
        if(pos>=3 && 
           isok(x,lst,m-pos+1) && 
           isok(x,lst,m-pos+2) && 
           isok(x,lst,m-pos+3)){
            dfs(x,lst,((now*3+1)*3+1)*3+1,pos-3,cnt+1);
        }
    }
}

// 处理单个测试用例
void solve(){
    memset(isbad,0,sizeof(isbad)); // 清空坏块标记
    memset(f,-0x3f3f3f3f,sizeof(f)); // 初始化DP数组为极小值
    cin>>n>>m>>k;
    for(int i=1;i<=k;i++){ // 读取坏块坐标
        int x,y;
        cin>>x>>y;
        isbad[x][y]=1;
    }
    f[0][0]=0; // 初始状态：0行0状态对应0芯片
    for(int i=0;i<n;i++){ // 处理每一行（从0到n-1对应第1到第n行）
        for(int j=0;j<pw[m];j++){ // 清空下一行的DP值
            f[(i+1)%2][j]=NINF;
        }
        for(int j=0;j<pw[m];j++){ // 遍历上一行所有可能状态
            if(f[i%2][j]<0) continue; // 跳过无效状态
            dfs(i+1,j,0,m,0); // 从当前行初始状态开始递归生成
        }
    }
    cout<<f[n%2][0]<<'\n'; // 输出最终结果：最后一行状态0的最大值
}

int main(){
    pw[0]=1; // 初始化3的0次幂
    for(int i=1;i<MN;i++){ // 预计算3的幂次数组
        pw[i]=pw[i-1]*3;
    }
    cin>>T;
    while (T--){
        solve(); // 处理每组数据
    }
    return 0;
}

一般来说，三进制优化DP使用DFS来进行编写。