状压DP

位运算为实现状态中包含元素子集的动态规划算法提供了一种高效且方便的方法，因为这样的状态可以存储为整数。接下来我们讨论将位运算与动态规划结合使用的例子。

例1. 最优选择

作为第一个例子，考虑下面的问题：给定 $k$ 种产品在 $n$ 天中的价格，我们希望每种产品恰好购买一次。然而，每天最多只能购买一种产品。最小总价格是多少？例如，考虑下面的情况（ $k=3$ ， $n=8$ ）：

	0	1	2	3	4	5	6	7
product 0	6	9	5	2	8	9	1	6
product 1	8	2	6	2	7	5	7	2
product 2	5	3	9	7	3	5	1	4

在这种情况下，最小总价格是 5：

	0	1	2	3	4	5	6	7
product 0	6	9	5	2	8	9	1	6
product 1	8	2	6	2	7	5	7	2
product 2	5	3	9	7	3	5	1	4

令 price[x][d] 表示产品 $x$ 在第 $d$ 天的价格。例如，在上面的情形中 price[2][3] = 7。然后，令 $\text{total}(S,d)$ 表示截至第 $d$ 天购买产品子集 $S$ 的最小总价格。利用这个函数，问题的解是

\text{total}(\{0\ldots k-1\},n-1).

首先， $\text{total}(\varnothing,d)=0$ ，因为购买一个空集不需要花费任何费用，并且 $\text{total}(\{x\},0)=\text{price}[x][0]$ ，因为第一天购买一种产品只有一种方式。然后，可以使用下面的递推式：

\text{total}(S,d)=\min\left( \text{total}(S,d-1), \min_{x\in S} \left(\text{total}(S\setminus x,d-1)+\text{price}[x][d]\right) \right)

这意味着我们要么在第 $d$ 天不购买任何产品，要么购买属于 $S$ 的一种产品 $x$ 。在后一种情况下，我们从 $S$ 中移除 $x$ ，并将 $x$ 的价格加到总价格中。

下一步是使用动态规划计算函数的值。为了存储函数值，我们声明一个数组

int total[1<<K][N];

其中 $K$ 和 $N$ 是足够大的常数。数组的第一维对应于一个子集的位表示。

首先， $d=0$ 的情况可以如下处理：

for (int x = 0; x < k; x++) {
    total[1<<x][0] = price[x][0];
}

然后，递推式转换为下面的代码：

for (int d = 1; d < n; d++) {
    for (int s = 0; s < (1<<k); s++) {
        total[s][d] = total[s][d-1];
        for (int x = 0; x < k; x++) {
            if (s&(1<<x)) {
                total[s][d] = min(total[s][d],
                                  total[s^(1<<x)][d-1]+price[x][d]);
            }
        }
    }
}

该算法的时间复杂度是 $O(n2^k k)$ 。

例2. 最短 Hamilton 路径

令 $dp[S][i]$ 表示访问子集 $S$ 中所有城市、并终止于城市 $i$ 的路线数量。转移为：

dp[S][i] = \sum_{x \in adj[i]} dp[S \setminus \{i\}][x] \text{ if $x \in S$}

其中 $S\setminus\{i\}$ 表示从子集 $S$ 中去掉城市 $i$ 。

时间复杂度： $\mathcal{O}(2^N\cdot N^2)$

合并子集

在一些问题中，对于集合 $S$ ，仅从 $S\setminus\{i\}$ 转移并不足够，而必须从 $S$ 的所有真子集转移。

虽然看起来需要进行 $\mathcal{O}(2^N\cdot 2^N)=\mathcal{O}(4^N)$ 次转移，实际上只有 $\mathcal{O}(3^N)$ 次！

为说明原因，来计算满足 $T\subset S$ 的有序对 $(T,S)$ 数量。无需直接计数，只要注意每个元素 $x$ 有三种状态：

同时位于 $T$ 和 $S$ 中；
两者都不属于；
位于 $S$ 中，但不位于 $T$ 中。

如果 $x$ 位于 $T$ 中却不位于 $S$ 中，那么 $T$ 就不是合法子集。

因为每个元素都有三种可能状态，所以总复杂度实际上是 $\mathcal{O}(3^N)$ 。

实现时可以使用一些位运算技巧：

for (int mask = 0; mask < (1 << n); mask++) {
	for (int submask = mask; submask != 0; submask = (submask - 1) & mask) {
		int subset = mask ^ submask;
		// do whatever you need to do here
	}
}

从 $\texttt{submask}$ 中减去 $1$ 时，最右侧的置位会变成 $0$ ，其右边的所有位都会变成 $1$ 。再与 $\texttt{mask}$ 按位与，就能去掉所有不属于 $\texttt{mask}$ 的多余位。在此过程中，计算表示集合差的 $\texttt{mask}\oplus\texttt{submask}$ ，即可按递增顺序得到所有真子集。

例3. Close Group

本题目标是把节点划分成若干集合，使每个集合中的节点都构成完全图。令 $\texttt{dp}[S]$ 表示将 $S$ 划分为若干部分、且每一部分都构成完全图时的最少部分数。

可以先找出哪些集合 $T$ 构成完全图，对这些集合令 $\texttt{dp}[T]=1$ ，否则令其为 $\infty$ 。朴素实现需要 $\mathcal{O}(2^N\cdot N^2)$ ；也可以把邻接表表示为位掩码，用位运算判断节点集合是否构成完全图，将复杂度降至 $\mathcal{O}(2^N\cdot N)$ 。

随后可按如下方式转移：

\texttt{dp}[S] = \min_{T \subset S} (\texttt{dp}[T] + \texttt{dp}[S \setminus T])

实现

时间复杂度： $\mathcal{O}(3^N+2^N\cdot N)$

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

int main() {
	int n, m;
	cin >> n >> m;
	vector<int> adj(n);
	for (int i = 0; i < m; i++) {
		int u, v;
		cin >> u >> v;
		u--;
		v--;
		// adjacency list represented as a bitmask
		adj[u] |= (1 << v);
		adj[v] |= (1 << u);
	}

	vector<int> dp(1 << n, INT32_MAX);
	for (int mask = 0; mask < (1 << n); mask++) {
		bool connected = true;
		for (int u = 0; u < n; u++) {
			if (((mask >> u) & 1) != 0) {
				// check if u is connected to all other nodes in mask
				if (((adj[u] | (1 << u)) & mask) != mask) {
					connected = false;
					break;
				}
			}
		}

		if (connected) { dp[mask] = 1; }
	}

	for (int mask = 0; mask < (1 << n); mask++) {
		for (int submask = mask; submask; submask = (submask - 1) & mask) {
			int subset = mask ^ submask;
			// submask has everything in mask but not in subset
			if (dp[subset] != INT32_MAX && dp[submask] != INT32_MAX) {
				dp[mask] = min(dp[mask], dp[subset] + dp[submask]);
			}
		}
	}

	cout << dp[(1 << n) - 1] << endl;
}

应用——质因数位掩码

基本思路

在一些数论问题中，用位掩码表示每个数的质因数会很有帮助。例如，集合 $\{6,10,15\}$ 可以表示为二进制的 $\{0b011,0b101,0b110\}$ ( $0b$ 前缀仅表示该数采用二进制表示)，各位分别对应能否被 $[2,3,5]$ 整除。

位掩码上的运算与这些整数上的运算存在如下对应关系：

按位与对应 GCD
按位或对应 LCM
遍历各位对应遍历质因数
遍历子掩码对应遍历因数

选择一个 GCD 为 $1$ 的集合，等价于选择一组按位与结果为 $0$ 的位掩码。例如， $\{6,10\}$ 的 GCD 不是 $1$ ，因为 $0b011\mathbin{\&}0b101=0b001\neq 0$ ；而 $\{6,10,15\}$ 的 GCD 为 $1$ ，因为 $0b011\mathbin{\&}0b101\mathbin{\&}0b110=0b000=0$ 。

例1. 最优选择​

例2. 最短 Hamilton 路径​

合并子集​

例3. Close Group​

实现​

应用——质因数位掩码​

基本思路​