概念：引入状压

在我们做题的过程中，有很多选或不选的题目，因为递归不好优化代码也长，我们可以使用状态压缩来解决这个问题。

状压状压，是状态压缩的缩写，向上面举的例子，状态就是选或不选，想要把 $n$ 个物品的状态压缩。能想到的就是二进制吧，我们把第 $i$ 个物品的状态放在第 $i$ 位。当然，状压可以不是二进制状态。

运用：熟悉状压

比如，我现在要枚举什么什么数量最大的组合，那么使用状压可以写出如下代码。

1
2
3
4
5
6
7
8
9
for(int i = 0; i < (1 << n); i++) {
    int tot = 0;
    for(int j = 0; j < n; j++) {
        if((1 << j) & i) {
            tot += a[j];
        }
    }
    ans = max(ans, tot);
}

复杂度 $O(n\times2^n)$ 这就是状压的最基本运用。

拓展：状态压缩DP

某一些 DP 的数据范围比较小，大概是 $O(n\times2^n)$ 能做的，那基本上就是状压DP了。

一般来讲，状压DP的状态都是二进制，当然不排除有3其他的，状压DP内容可变性很大，具体看题目领会。

实践：状压例题

见以下标签喵！