状压
意义
顾名思义：状态压缩
什么是状态压缩呢？
简单来说就是用一个\(n\)进制数，每一位上代表着某一个节点或是其他东西地状态。
常见的都是二进制，因为二进制明显更加好写，毕竟那么一大堆位运算可不是摆设。
常见用法
接下来的运算均从第0位开始
-
判断一个数字x二进制下第i位是不是等于1。
方法：(1 << i) & x/(x >> i) & 1 -
将一个数字x二进制下第 i 位更改成 1。
方法：x = x | (1 << i) -
将一个数字x二进制下第 i 位更改成 0。
方法：x = x & ~(1 << i) -
把一个数字二进制下最靠右的第一个1去掉。
方法：x = x & (x - 1) -
统计二进制中 1 的个数
方法：__builtin_popcount(x)
最简单的例题
题面描述
给定 \(n\) 个非负整数 \(a_1,a_2,a_3,\ldots,a_n\)。请你从中任意选择恰好 \(m\) 个整数，使得这 \(m\) 个整数的和不超过 \(k\)。
请求出有多少种不同的选择方案。
做法
-
我们定义第\(i\)位为\(0\)时，代表该数没有被选。
-
反之，当第\(i\)位为\(1\)时，代表该数已被选。
恰好\(m\)个整数我们可以用__builtin_popcount(x)函数来算有多少个\(1\)
- 如果不为\(m\)
直接退出，去遍历下一个状态 - 如果为\(m\)，就往下遍历。
每一次只需要找哪些位为\(1\)，并把对应的数加起来即可。
找哪些位为\(1\)，有两种做法。
- 每次找到最右边的\(1\)，加完对应的数再减掉。
- 直接遍历
from 1 to n，去找哪些位为\(1\)
代码
戳我
int a[N];signed main() {int n = re, m = re, k = re;for (int i = 1; i <= n; i++) a[i] = re;int ans = 0;for (int i = 0; i < (1 << n); i++) if (__builtin_popcount(i) == m) {int cnt = 0;for (int j = 1; j <= n; j++) if ((i >> j - 1) & 1) cnt += a[j];ans += cnt <= k;}wr(ans), endl;
}
状压DP
意义
也是顾名思义，以某个状态去记录答案。
简单例题 最短 Hamilton 路径
做法
定义\(dp_{s,j}\)表示在\(S\)这个集合内，以\(j\)为终点的最短距离。
状态转移方程式：$$dp_{s,j} = min(dp_{i \oplus (1 << j),k} + graph_{k,j}) 且 j,k \in s,j \not= k$$
代码
别戳我
int n;
int a[N][N];
int dp[M][N];//表示集合S内的最短路径signed main() {n = re;for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) graph[i][j] = re;memset(dp, 0x3f, sizeof dp);dp[1][0] = 0;for (int s = 1; s < (1 << n); i++) {for (int j = 0; j < n; j++) {if ((s >> j) & 1) {for (int k = 0; k < n; k++) {if ((s ^ (1 << j)) >> k & 1) dp[s][j] = min(dp[s][j], dp[s ^ (1 << j)][k] + graph[k][j]);}}}}wr(dp[(1 << n) - 1][n - 1]);
}