温馨提示：学习状态压缩 $dp$ 需要有一定的位运算基础，但是只要会用就行。

第一章节 基础的状态压缩dp

先从几道例题开始讲起

luogu P4329

题意简述：
给出一个 $n\times n$ 的数字网格，让你在这 $n\times n$ 个数中选出 $n$ 个，满足他们没有任意两个选出的位置在同一行或者同一列，问这些数的乘积最大是多少？

数据范围：
$1\le n\le 20,1\le a_{i,j}\le 100$

很显然我们可以把 满足他们没有任意两个选出的位置在同一行或者同一列 理解为每一行都分别选择一个数字，并且满足他们没有数字在同一列，求满足这个条件的最大乘积。于是此时我们可以来 $dp$，状态设计：
$dp[0/1][0/1][0/1].....[0/1][0/1]$
状态里的第 $i$ 维表示在我们已经选的那些行里，第 $i$ 列有没有被选过，$0$ 表示没有，$1$ 表示选了。那么此时我们考虑转移：
对于$dp[a_1][a_2][a_3].....[a_{m-1}][a_m]$，我们考虑在这个基础上我们又选择了哪一列，假设其是第 $j$ 列，首先需要判断 $a_j$ 是否为 $0$，如果为 $1$ 因为已经被选了，就不能再选了。如果可以，那么 $dp[a_1][a_2][a_3].....[a_{m-1}][a_m]$ 显然可以转移到：
$dp[a_1][a_2][a_3]..[a_j]..[a_{m-1}][a_m](a_j=1)$
即：
$dp[a_1][a_2][a_3]..[a_j]..[a_{m-1}][a_m](a_j=1)$ =$max(dp[a_1][a_2][a_3]..[a_j]..[a_{m-1}][a_m](a_j=1),dp[a_1][a_2][a_3]..[a_j]..[a_{m-1}][a_m](a_j=1)\times value)$
这里的 $value$ 是什么呢，是我们新选的第 $j$ 列的那个数，他的行是什么呢，即$a_1,a_2,....,a_m$ 中 $1$ 的个数（即我们已经选择过的行数，设他为 $cnt$），因为我们是按照行的顺序来 $dp$ 的，那么我们已经考虑了 $cnt$ 行，显然我们现在正在 $dp$ 第 $cnt+1$ 行，所以这个 $value$ 就等于 $a_{cnt+1,j}$
接下来是答案，答案即我们把所有的行都考虑完了，对于每一行，一共选出来了 $n$ 列，我们并且知道他们没有重复的，那么显然这些列的编号是一个 $1$ 至 $n$ 的排列，所以答案就是 $dp[1][1].....[1][1][1]$。

可是发现了吗，这里的状态有 $n$ 个，你写的过来吗？
此时我们发现，他的状态只有 $0$ 和 $1$ 两种，我们可以将这 $n$ 维状态看成二进制中的位，二进制位上的 $0/1$ 就表示 $dp$ 状态里的那些 $0/1$，即把状态压缩成了一个二进制数，这就是状态压缩 $dp$。
那么此时我们再用二进制数看看怎么来实现刚才的转移以及答案的表示。首先转移，设当前 $n$ 位的状态所表示的二进制为 $s$，我们判断一个 $j$ 是已经用过了即二进制中的第 $j$ 位，是否是 $1$，那么这个就用$s>>(j-1)$ & $1$ 即可获取第 $j$ 位，判断一下即可。那么对于可行的一个列 $j$ ，我们来尝试转移。那么转移就是对于 $s$，设把 $s$ 二进制中的第 $j$ 位变成 $1$ 后的二进制数为 $s^{\prime }$，那么 $dp[s^{\prime }]=dp[s]\times a_{cnt+1,j}$，这里的 $cnt$ 即 $s$ 二进制中 $1$ 的个数，对应前面 $n$ 维 $dp$ 里的 $n$ 个维里 $1$ 的数量。那么此时还有一个问题: $s^{\prime }$ 怎么得到呢？很简单，显然 $s^{\prime }$ 就是 $s$ 在加上一个第 $j$ 位所对应的权值，即 $s+2^{j-1}$。
接下来，答案怎么表示呢？显然 $dp[1][1][1]...[1][1][1]$ 的二进制为 $2^0+2^1+2^2+....+2^{n-1}$，这个小学数学就学过吧，这个东西等于 $2^n-1$，所以在压缩后的状态里即 $dp[2^n-1]$

Code：

/*
Problem ID: luogu P4329
*/
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
void tomin(int& x, int y){x = min(x, y);}
void tomax(int& x, int y){x = max(x, y);}
int lowbit(int x) {
    return x & (-x);
}
const int maxn = 25, maxm = 1 << 20;
double a[maxn][maxn], dp[maxm];
int n; 
int count(int x) { //普通的lowbit获取1的个数
//你也可以写朴素的方法
    int ans = 0;
    while (x) x -= lowbit(x), ans++;
    return ans;
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ ) {
            cin >> a[i][j];
            a[i][j] /= 100; //这个题目里要求是百分数，你可以忽略他，不要给他误导了
        }
    dp[0] = 1;
    for (int i = 0; i <= (1 << n) - 1; i ++ ) {
        int cnt = count(i); //获取1的个数
        for (int j = 1; j <= n; j ++ )
            if (!(i >> (j - 1) & 1))
                dp[i + (1 << (j - 1))] = max(dp[i | (1 << (j - 1))], dp[i] * a[cnt + 1][j]); //此处你可以写i + (1 << (j - 1)) 也可以写 i | (1 << (j - 1))，但是平时建议你写 i | (1 << (j - 1))
    }
    printf("%.6lf", dp[(1 << n) - 1] * 100); //注意：*100也是题目里的要求，你也可以忽略他
    //输出对应状态
    return 0;
}

我们在写一道状态压缩 $dp$ 的水题练练手。

luogu P1433

题意简述：
平面上有 $n$ 个点，你最开始在 $(0,0)$，你需要到达所有的点，问这个最短距离。

这道题也是一道经典的状态压缩 $dp$ 水题。
首先我们设计状态，因为我们关心的是当前我已经走了哪些点了以及我现在在哪个点，所以我们把这两个东西都考虑进我们的状态里就行了。所以由此我们可以推出状态：
$dp[s][now]$， $s$ 表示当前二进制状态，表示每一个位置是否已经经过了，$now$ 则表示当前我在哪一个点，那么显然答案就是$min(dp[2^n-1][i])$。
接下来考虑转移：
对于 $dp[s][j]$，我们考虑我们下一个去哪个点，设我们去点 $k$，那么首先的条件是我们之前没有去过点 $k$ 因为如果去过了，没必要浪费啊，所以我们有一个显而易见的策略，也就是不走已经走过的点。所以我们判断 $s$ 二进制中的第 $k$ 位是否为 $0$ 如果是那么我们考虑转移方程：
设 $s^{\prime }$ 为把 $s$ 二进制中的第 $k$ 为变成 $1$ 后的状态，那么可以得到状态转移方程：
$dp[s^{\prime }][k]=min(dp[s^{\prime }][k],dp[s][j]+dis(j,k))$
$dis(j,k)$ 即从 $(x_j,y_j)$ 走到 $(x_k,y_k)$ 的欧几里得距离。
这就完了？ 不是的。
这道题我们需要手动初始化，也就是我们从 $(0,0)$ 走到 $i$ 的这样的状态，也就是 $dp[2^{i-1}]=dis(0,i)$，$dis(0,i)$ 就是从 $(0,0)$ 走到 $(x_i,y_i)$ 的欧几里得距离。
至此，这道题就做完了，十分的简单，适合练手。

Code:

/*
Problem ID: luogu P1433
*/
#include <bits/stdc++.h>
#define pb push_back
#define ll long long
using namespace std;
void tomin(int& x, int y){x = min(x, y);}
void tomax(int& x, int y){x = max(x, y);}
const int maxn = 20, maxm = 1 << 15;
double x[maxn], y[maxn], dp[maxm][maxn];
double dis(double a, double b, double c, double d) {
    return sqrt((a - c) * (a - c) + (b - d) * (b - d));
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> x[i] >> y[i];
    for (int i = 0; i <= (1 << n) - 1; i ++ )
        for (int j = 1; j <= n; j ++ )
            dp[i][j] = 1e9;
    for (int i = 1; i <= n; i ++ ) dp[1 << (i - 1)][i] = dis(0, 0, x[i], y[i]);
    for (int i = 1; i <= (1 << n) - 1; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            if ((i >> (j - 1) & 1)) {
                for (int k = 1; k <= n; k ++ )
                    if (!(i >> (k - 1) & 1))
                        dp[i + (1 << (k - 1))][k] = min(dp[i + (1 << (k - 1))][k], dp[i][j] + dis(x[j], y[j], x[k], y[k]));
            }
        }
    }
    double ans = 1e9;
    for (int i = 1; i <= n; i ++ )
        ans = min(ans, dp[(1 << n) - 1][i]);
    printf("%.2lf", ans);
    return 0;
}

第二章节 有后效性的状态压缩dp

对于有后效性的状态压缩 $dp$，我们怎么办呢 $qwq$？

luogu P2622

题意简述：
有 $n$ 栈灯，最开始全都开着，有 $m$ 种开关，你可以使用他们，问最少使用多少次，可以让所有灯都关掉。
此时会发现一个比较板子的东西：我们可以把 $n$ 个灯的状态记成二进制，一个位上的 $0/1$ 表示关灯或者开灯，所以我们可以用数 $s$ 来表示一组 $n$ 个灯的状态。为了方便起见，那么我们的状态就是对于一位如果是 $1$ 就表示这一位已经关掉了，如果是 $0$ 就是这一位没关掉。那么最初的状态就是全都是 $0$ 的一个二进制数，十进制中就是 $0$，我们用 $dp[i]$ 表示从最初是的状态变成 $i$ 这个状态的最少操作次数，那么最初的状态就是 $dp[0]=0$。可是此时你会发现，这个 $dp$ 是有后效性的。
那么此时我们怎么解决呢？我们搭配上搜索就行了
我们把已经确定的状态存在队列里，然后我们进行 $bfs$
对于我们现在队列里的一个状态 $s$，现在我们看看他可以选择一个操作变成什么，设我们通过第 $i$ 种操作得到的状态为 $s^{\prime }$，那么 $s^{\prime }$ 可以由 $s$ 进行一次得到，即 $dp[s^{\prime }]=min(dp[s^{\prime }],dp[s]+1)$ 如果 $dp[s]+1$ 比之前更优秀，那么我们就可以首先把他更新，然后把他放进队列里，这是因为要再次把他的后继状态更新。
最后答案就是 $dp[2^n-1]$。

Code:

/*
Problem ID: luogu P2622
*/
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 15, maxm = 105, maxp = 1 << 10;
int n, m, a[maxm][maxn], cd[maxm], cq[maxm];
int dp[maxp];
bool vis[maxp];
int main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            cin >> a[i][j];
            if (a[i][j] == 1)
                cd[i] |= (1 << j - 1);
            if (a[i][j] == -1)
                cq[i] |= (1 << j - 1);
        }
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    queue<int> q; q.push(0);
    while (!q.empty()) {
        int t = q.front(); q.pop(); vis[t] = false;
        for (int i = 1; i <= m; i ++ ) {
            int v = ((t | cd[i]) & (~cq[i]));
            if (dp[v] > dp[t] + 1) {
                dp[v] = dp[t] + 1;
                if (!vis[v])
                    q.push(v), vis[v] = true;
            }
        }
    }
    if (dp[(1 << n) - 1] == 0x3f3f3f3f)
        cout << -1;
    else
        cout << dp[(1 << n) - 1];
    return 0;
}

至此，这就解决了。

第三章节 较复杂的状态压缩dp

本章节讲一些二维的比较复杂度的状态压缩 $dp$。

luogu P1896

题意简述：
有一个 $n\times n$ 的网格，让你在里面放 $K$ 个国王，一个国王可以攻击他周围的 $8$ 个网格，问有多少种方案可以满足不会有两个国王会互相攻击。

对于每一行的每一个位置，我们可以选择放或者不放，我们用 $0$ 表示不放，用 $1$ 表示放，那么显然，我们可以用一个二进制数代表一行的状态，因此我们可以设计出状态：$dp[i][s][k]$ 表示现在考虑到第 $i$ 行，第 $i$ 行的状态是 $s$，我们已经在前 $i$ 行放了 $k$ 个国王的合法方案的方案数。
那么对于 $s$，我们首先要判断他是否会在一行内会有互相攻击的情况，如果有，那么这种情况一定不可能，因为这种情况一定不合法。

判断合法的方式：
我们将这个二进制数左移一位然后在与上他本身，如果>0，那么显然就有相邻的（攻击的）。因为如果>0,那么也就是说有1被左移后和原来的一个1重合了，说明他们相邻。

如果合法，那么此时我们枚举上一行的状态 $s^{\prime }$，判断 $s^{\prime }$ 和 $s$ 是否会有国王起冲突。如果不会起冲突，那么我们进行转移：枚举我们在前 $i$ 行放了 $l$ 个国王，然后我们在第 $i$ 行放了 $count(s)$ 个国王，那么前 $i-1$ 行就放了 $l-count(s)$ 个，即 $dp(i,s,l)+=dp(i-1,s^{\prime },l-count(s))$。这里 $count(s)$ 表示 $s$ 二进制中 $1$ 的个数。

判断两行合法的方式：
首先他们本身没有重合（即两个与起来等于 $0$），并且没有其中一个状态里的1的两边的位置在另一个状态里是$1$ （$A$ 状态左移一位与上 $B$ 状态等于0，并且 $B$ 状态左移一位与上 $A$ 状态等于0）

时间复杂度 $O(n{2}^n{2}^{n}K)$

复杂度爆炸！

怎么优化呢？
很显然我们在这里多次判断了一行内是否合法，所以我们那可以在最开始就预处理出来所有在一行内不会冲突的状态，显然会有很多状态被淘汰掉，设合法的数量为 $tot$，时间复杂度：
$O(nto{t}^{2}K)$
答案为 $sum(dp[n][一个合法状态][K])$

Code:

/*
Problem ID: luogu P1896
*/
#include <bits/stdc++.h>
#define ll long long
#define pb push_bck
using namespace std;
void tomin(int& x, int y){x = min(x, y);}
void tomax(int& x, int y){x = max(x, y);}
bool check2(int s, int t) {
    return (s & t) == 0 && ((s << 1) & t) == 0 && (s & (t << 1)) == 0;
}
bool check1(int s) {
    return (s & (s << 1)) == 0;
}
const int maxn = 10, maxk = 105, maxm = 1 << 9;
int n, K, ok[maxm], tot;
ll dp[maxn][maxm][maxk];
int lowbit(int x) {
    return x & (-x);
}
int count(int x) {
    int ans = 0;
    while (x)
        x -= lowbit(x), ++ans;
    return ans;
}
int main() {
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n >> K;
    for (int i = 0; i < (1 << n); i ++ )
        if (check1(i))
            ok[++tot] = i;
    for (int i = 1; i <= tot; i ++ )
        dp[1][ok[i]][count(ok[i])] = 1;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= tot; j ++ )
            for (int k = 1; k <= tot; k ++ ) {
                if (!check2(ok[j], ok[k])) continue;
                int C = count(ok[j]);
                for (int l = K; l >= C; l--)
                    dp[i][ok[j]][l] += dp[i - 1][ok[k]][l - C];
            }
    ll ans = 0;
    for (int i = 1; i <= tot; i ++ )
        ans += dp[n][ok[i]][K];
    cout << ans;
    return 0;
}