状态压缩 DP

David_Mercury · 2023-07-11 15:11:16 · 个人记录

一、概念 \& 思想

状态压缩 DP 是指将状态的一部分压缩为一个 K 进制整数的算法。

• 为什么要用？ 当要表示一个状态所需维数很多，给数组多开维就会很麻烦的时候；或者说压缩了就操作更便捷、更快的时候。

• 什么时候能用？ 位数不要过多（很多时候都为 12），状态最大值很小 (\le K)。

• 怎么用？ 除了压缩整数，可能还要额外开维维护其他信息。位运算也是这里的常用技巧。

二、应用

1. Hamilton 路径：最短Hamilton路径、P1433 吃奶酪、旅行商问题

   最简单的状压 DP 应用。二进制数 i 表示哪些点被经过了，j 表示经过的最后一个点，目标：1 \rightarrow 2^n-1(111\dots1)。

2. 填充网格图形

   • P1879 [USACO06NOV] Corn Fields G

     比较板。两个技巧：(j<<1)&j 判断是否有相邻 1，a[i]&j 判断是否种到贫瘠土地。

   • T164757 【状压】棋盘覆盖

     转移用到了两个技巧。j&k == 0 不用说；j|k 的结果中，0 必须为偶数个（预处理）。

     另外，哪个状态设置为 0 哪个设置为 1 对我们的位运算更有帮助也是值得推敲的。

   • P2704 [NOI2001] 炮兵阵地

     • 解法一：使用二进制表示炮兵放置情况，枚举前两个阶段。时间复杂度看似 O(2^{3m})，但若对满足条件（相邻 1 相隔至少 2）的数进行预处理后，可以发现满足条件的实际很少。这体现了预处理能够帮我们预先排除不符合条件集合。

     • 解法二：三进制表示，DFS 转移。（看似复杂度高，实则因为多重限制条件，满足的很少）

3. 其他

   作者太逊，还有好多没写，总结不出个什么来，就先咕了 >\frown< ~~~

   • P3052 [USACO12MAR] Cows in a Skyscraper G

   • P3959 [NOIP2017 提高组] 宝藏

   • P4163 [SCOI2007] 排列

   • P2831 [NOIP2016 提高组] 愤怒的小鸟

   • P2167 [SDOI2009] Bill的挑战

   • P2157 [SDOI2009] 学校食堂

   • P2566 [SCOI2009] 围豆豆