状压 DP

Vision271 · 2022-11-03 08:36:04 · 个人记录

概述

• 状压 DP 是以状态含有某种意义上的状态压缩为特点的一类 DP。

• 所谓状态压缩，通常指的是将各个元素的状态从常规的 vector 等编码映射为一个 id 即抽象的状态。

  • 较为常见的方式是压缩为一个 n 位 k 进制数，其中 n 为元素数，k 为每个元素的状态数（中的最大值，理由见下），0\sim k^n-1 分别对应一种状态。

  • 固然可以 map，但是多一个 \log。

  • 当各元素状态数不一的时候通常暴力编码建图连边（即将转移实际地建成边），不会使用简单的进制状压，因为无效状态太多。

  • 也有时“状态”是高度抽象的，如 \text{P2051 [AHOI2009] 中国象棋}，此时几乎可以认为其是线性 DP。

  • 事实上将状压的状态不断简化就归约到线性，随着线性的状态难以规约决策就升维到状压，两者都指向 DP 的本质。

  • 这里的升维不一定是增多维数，也可能是将已有维度变得更复杂，包含更多信息。

  • 不过，不论如何，下文中，如无特别声明，默认使用进制状压。这才是最经典的狭义状压 DP。

• 状态设计通常包括一个压缩的状态 sta，如果是 k 进制数，则也称为 k 进制状态。

• 初始化通常为 dp_{start,\dots}=\dots，这里的 start 是初始状态，通常为 empty 即 0。

• 转移上以状态为基，一般根据压物品和压属性有着不同的转移：

  • 压物品：逆推，dp_{sta,\dots}=\dots，具体细节看是什么类的问题。

  • 压属性：

    • 比较舒服的是顺推，dp_{i,sta}\to dp_{i+1,sta},dp_{i+1,to}，这里的 to 是原状态加入 a_{i+1} 后的结果状态。

    • 鉴于一般是逐物品枚举，无非选或不选，谈不上“优化转移复杂度”一说，所以就先不考虑很麻烦的状态转移方程了，毕竟得算除去某个物品的状态，而状态可能只满足结合性，不满足差分性。

    • 事实上，即使将转移方程写出来，转移来源也很可能是离散的，谈不上优化。

• 更具体的，我们还是在下面分几类来谈。特别需要指出的是，很难的一些复杂状压 DP 我也把它们随便地分了个类，但它们也可以单独分一类叫“复杂状压 DP”，故——我是说，不要受问题形式限制。不要抱死依赖和需求不放。

依赖式问题

• 典型代表如 \text{P5005 中国象棋 - 摆上马} 和 \text{P2051 [AHOI2009] 中国象棋}，前者为经典版，后者为魔改版。

• 特点是给出 n 个物品，物品有价值 w，物品之间有一些依赖关系，求选取方案的最大总价值或方案数。

  • 所谓依赖，可能是物品之间互相依赖对方存在或不存在。

  • 依赖可能不是直接连边来实现的，而是藉由对空间的占据等中间元素作为中继来构成依赖。

• 状态通常为 dp_{sta,\dots} 表示当前选取了 sta 对应的物品集/有着 sta 对应的要素集（即作为中继的中间元素的集合），最大总价值是多少。视情况可能有各种辅助维。

• 初始化为 dp_{start,\dots}=v_{start}（可能有必选之类的作为起始状态）。

• 状态转移：

  • 压物品： dp_{sta,\dots}=\max_{j\in ava}(dp_{j,\dots}+w_{j,sta})，其中 ava 为 sta 可接受的来源状态。

  • 压属性：和概述讲的基本一样，不复制了。

  • 这里有一个有趣的问题：显然状压 DP 可以不管 sta 的合法性暴力转，最后遍历所有 sta 检查合法性来计算答案。

  • 然而有的题目里有更好的性质：

    • 如果 sta 合法，那么 sub\subseteq sta 都合法（这里的包含关系在进制状压下就是简单包含，编码状压下可能是某种拓扑序关系的上下游）。

    • 如果 sta 不合法，那么 sup\supseteq sta 都不合法。这里 sup 是超集 superset 的简写。

  • 显然，我们可以基于此只从合法点出发来转移，可以期望减小一定常数。然而有没有基于这种性质的更优解？

  • 事实上，这让我想起拟阵贪心的定义。也许带悔就可以？

• 复杂度 O(k^n)，辅助维开销具体问题具体分析。

P5005 中国象棋 - 摆上马

• 题意：在 n\times m 的棋盘上摆任意个中国象棋的马（考虑蹩马腿的影响），求总方案数。

• 数据范围：原题 n\leqslant 100,m\leqslant 6。可做 n=m=10。

• 依赖关系是马之间依赖对方的不攻击（不存在）。

• DP 设计如下：

  • 状态设计：dp_{i,sta1,sta2} 表示考虑完前 i 行，第 i,i-1 行的放置情况分别为 sta1,sta2 的总方案数。

    • 大部分这种逐行转移的都可以滚掉第一维，后面不再专门指出。

  • 初始化：dp_{0,0,0}=1。

  • 状态转移：

    • 首先有一个很 naive 的暴力顺推，总复杂度 O(2^{3m}\times n)，足够通过本题，就是写起来不是一点恶心（考虑 O(2^{3m}) 预处理矛盾情况，为了实现这个预处理可以 O(6\times 4) 地先算每个孤立马和已有 sta 的矛盾情况，然后整）。

    • 然后可以 FMT 优化，但有一些问题，主要是以下两个：

      • 1.怎么预处理极大不矛盾集合，总不能 O(2^{3m}) 吧？

      • 2.求的是子集和吗？当 sta1'\subseteq sta1,sta2'=sta2 时，是否会有 sta2 中某个本来被蹩马腿的现在不被蹩了，于是矛盾了？

    • 解决办法：暴力枚举 sta1。

      • 于是对于给定的 sta1，sta2 这边可以子集和。问题变成暴力枚举 sta1，然后 FMT 卷 sta2。

    • 对于每个 (i,sta1) 对需要 FMT 一次，总复杂度 O(2^m\times m\times 2^m\times n=2^{2m}\times m\times n)，前项是次数后项是 FMT 复杂度。可以做 n=m=10。

    • FMT 相关可以参看复合式问题一节的 \text{P1896 [SCOI2005] 互不侵犯}，有较详细的说明。

P2704 [NOI2001] 炮兵阵地

• 占据范围为伸出长度为 2 的十字，有些地方是障碍不能摆。其余平凡，还是双 sta 式，略。

• 依赖关系为依赖不攻击（不存在）。

• 复杂度也同上，不过是增强版的数据范围。当然暴力转也能过，因为可以预处理建图，有效状态和转移并不多。

P2051 [AHOI2009] 中国象棋

• 题意：摆炮。

• 数据范围：n,m\leqslant 100。

• 依赖关系同上。

• 这其实是个诈骗题。谨记一点：除非有不得不状压的理由，否则不要状压。

• 对于炮/车/...来说，放在了哪一列并不重要，我们只关心放了多少列。

  • 作为对比，之所以放王/马的时候要压放在哪里，是因为每列并不同质，靠边的和靠中间的影响并不一样。可以考虑 m=5 时的 01000 和 00100 的差异，其中 1 处为王。

  • 至于炮兵啊...因为它有障碍，可能根本不能放，所以列与列不同。

• 于是设计 DP 如下：

  • 状态设计：dp_{i,j,k} 表示考虑完前 i 行，有 j 列放了一个炮，有 k 列放了两个炮的总方案数。

  • 初始化：dp_{0,0,0}=1。

  • 状态转移方程：较为复杂，考虑分类讨论。

    • 本行没有放炮：dp_{i-1,j,k}。

    • 放了一个：dp_{i-1,j+1,k-1}\times (j+1)+dp_{i-1,j-1,k}\times (m-j+1-k)。

    • 放了两个：dp_{i-1,j-2,k}\times C(n-j+2-k,2)+dp_{i-1,j-1,k-1}\times ... 不想写了总之就是把选哪些列的系数 C 出来。

    • 这些求和就是 dp_{i,j,k} 了。

• 时间复杂度 O(nm^2)。

• DP 的本质是：

  • 将决策过程中的（复杂的，实际的）状态抽象为一组（simple and stupid 的）DP 状态，将决策的过程抽象为这些状态之间的转移（实质上同构于图论中的“点-边”模型，点即元素是状态，边即元素的二元关系是转移）。

  • 将实际上极不同的状态根据其关键信息的同异归类、压缩到少得多的 DP 状态里。

  • 采用的 DP 状态可能是复杂的进制状压或编码状压状态，也可能是高度压缩、抽象、简化的线性状态。如本题的 DP 状态就高度线性。

  • 以此，将朴素决策也即搜索的指数级复杂度规约到可以接受的多项式时间内。

• 故时刻谨记，不要看到什么信息就把什么信息记录下来（指塞进 DP 状态里），而是要去繁就简，执简驭繁。

• 对每个包含在状态中的信息，我们都要提问：你的必要性是什么？舍弃你就无法决策/无法正确地刻画过程了吗？如果不必要，把你舍弃能否获得更精简的状态？

• 通过这样的极度抽象，将复杂的问题简单化。

P3226 [HNOI2012] 集合选数

• 题意：

  • 这道题我审错题了...我们后面在 \text{P2150 [NOI2015] 寿司晚宴} 那里谈谈我以为的题及其解法。

  • 好了，说回来。定义一个集合 S 合法，当且仅当 \forall i\in S,2i,3i\notin S。

  • 求 [1,n]\cap N 的合法子集数量。

• 数据范围：原题为 n\leqslant 10^5，考虑到实际上暴力转移只跑了近 700ms 应该可以更大，但本题的复杂度分析过于恶心，所以不去算可做的上界了。

• 本题实际上是一个妙妙构造题。\forall i,(i,2i),(i,3i) 构成一组双向不存在式依赖（矛盾），但显然直接压根本无法接受。

• 注意到考虑能否加入 i 的时候关心的东西其实很少，只有 sta 中的两个信息，于是（鬼知道为什么于是）想到这么一种构造：

  • 那么发现每个矩阵内部的元素互相有限制，限制为相邻元素不能同时选。基于网格图的优秀性质，考虑压当前行选了哪些。

• 故设计 DP 如下：

  • 状态设计：dp_{i,sta} 表示考虑完矩阵第 i 行，当前行选取情况为 sta 的总选取方案数。

  • 初始化：dp_{0,0}=1。

  • 状态转移方程：dp_{i,sta}=\sum\limits_{from\subseteq sta\oplus full} dp_{i-1,from}。老规矩 FMT。

• 则显然答案就是 \prod\limits_{i=1}^k (\sum\limits_{j=0}^{full_i} dp_{n_i,j})，其中 k 为矩阵数。

• 复杂度 O(\text{能过})。

  • 反正无论如何，最大矩阵的贡献应该不超过 O(2^{\log_3 n}\times\log_3 n \times \log_2 n)\approx 2^{10}\times 10\times 17=1.7\times 10^5，前面是 FMT 后面是次数，显然足够小。别在意那么多啦。

  • 其实还是可以在意一下。记 2^{\log_3 n}=K，则有 \log_3 n=\log_2 K，换底公式乱搞后 \log_2 K=1.58\log_2 n，显然复杂度不超过 O(n\log^2)。

  • 不过事实上...这个东西是低于线性的，n=10^8 时 \approx 6\times 10^7。

  • 不过也显而易见的是，只考察最大矩阵一定不对。大约有 \dfrac{n}{\ln n} 倍常数？谁知道呢...总之不要在意啦，休息一下吧。

P2150 [NOI2015] 寿司晚宴

• 题意：求满足 S_1,S_2\subseteq [2,n]\cap N \And \forall i\in S_1,j\in S_2,i\perp j 的 (S_1,S_2) 对数量。

• 数据范围：n\leqslant 500。

• 依赖关系是依赖不互质的数不存在。

• 数论题，准确的说是整除与同余相关，那么无脑考虑记录质数。

• 显然直接压是不行的，考虑压小质因子。

  • 任何一个 \leqslant n 的合数都有至少一个 \leqslant \sqrt{n} 的因数。

  • 故可以考虑只压 \leqslant \sqrt{n} 的小质数，根据素数个数定理，小质数数量 \sim \dfrac{\sqrt{n}}{\ln \sqrt{n}}。

• 所以我们可以...等等。这不对。考虑一下，万一把 23 和 46 选到了两边，怎么办？

• 让我们再设法从根号分治这只橙子上榨出些汁子来：

  • 任何一个 \leqslant n 的合数都至多只有一个 \geqslant \sqrt{n} 的质因数。

  • 这代表着什么？这代表着，在把 <\sqrt{n} 的质因数压完即去除影响后，问题退化成一个朴素分组背包，分的组就是最大质因数（最大质因数 <\sqrt{n} 的可以认为是第零组）！

• 所以将小质数编码，设计 DP 如下：

  • 状态设计：f_{i,sta} 表示考虑了前 i 组，当前每个小质数是没有选/在 S_1 中/在 S_2 中的方案数。

  • 初始化：f_{0,0}=1。

  • 状态转移：顺推考虑每一组，将 f_{i-1} 作为初始值，然后把 g_{end} 取出来作为 f_i，其中 g_{end} 表示考虑完组内所有数的组内 DP 结果。

• 组内 DP：

  • 状态设计：g_{i,sta,0/1/2} 表示考虑完当前组的前 i 个，每个小质数的状态，当前组对应的大质数的状态。

  • 初始化：记当前组为第 k 组，则 g_{0,sta,0}=f_{k-1,sta}。

  • 状态转移：

    • 分讨 i+1 不选/入 S_1/入 S_2，检验合法性，计算出目标状态然后转移。

    • 具体实现可以对每个数预处理一个 sta 表示其含的小质数集合。

• 复杂度为 O(\sim 3^\frac{\sqrt{n}}{\ln \sqrt{n}}\times n)，可以接受的数据上界大约为 n=1354，总之足够通过本题。

• 说回那个我看错题意的集合选数，我以为是任意倍都矛盾，即集合内得互质。于是相当于一个 2 进制 sta 的寿司晚宴（寿司晚宴其实我写的是两个二进制状态，因为好写）。

P4363 [九省联考 2018] 一双木棋 chess

• 题意略。

• 需求是左上都放过。

• 手推容易发现，已有状态集，我是指下过棋的地方，构成一个从左上角延伸出来的阶梯形，即 \forall i<n,to_i\geqslant to_{i+1}，这里 to 是本行的极右延伸。

• 于是暴搜之，发现只有 184756 的状态数。直接暴力记搜（这里我采用了双射进制哈希然后 u_map 暴力创过去），转移复杂度 O(10)，属于是放在这有点画风不符的题目了。

• 本题的数据显然可以进一步加强，我们谈谈更优的做法：\alpha-\beta 剪枝搜索。直接非常符合直觉地正着搜就行，大概起步能通过纸面复杂度 10^9 的数据范围。

P3160 [CQOI2012] 局部极小值

• 题意：给出一个 n\times m 的矩阵，求将 1\sim n\times m 不重地填入其中使得有且仅有某些地方是局部极小值的方案数。

  • 称一个格子中的数是局部极小值，当且仅当其是以其为中心的九宫格中最小的数。

• 数据范围：n\leqslant 4,m\leqslant 7。

• 依赖关系是大小上的偏序关系。

• 首先我们根本没见过 2^{28} 的复杂度，尽管它确实 \approx 2.7\times 10^8。

• 设法设计 DP，发现整个过程过于复杂，考虑约束它使得它可刻画。两种思路：

  1. 逐行转移；

  2. 从小到大填数。

• 显然后者更自然，也更 specific。基于此，我们做一点简单的题意转化，记局部极小值为 x，非局部极小值为 o。

  • x：所在九宫格内最早填上。

  • o：不是所在九宫格内最早填上，且晚于九宫格内任意 x。

    • 可以进一步抽象成一类 o 和二类 o：

    • 一类 o：周围有 x。比周围的 x 晚就好。

    • 二类 o：周围无 x。不是最先填就好。

• 基于此，我们已经可以做 O(2^{nm}\times (nm)^2) 的朴素 DP 了。发现 (nm)^2 来自：

  1. 枚举填到谁了；

  2. 枚举填到哪里去。

• 以普遍理性而论，1 的复杂度肯定消不掉（bitset 等盘外招当然不在讨论之列）。这就告诉我们这个状态没前途，得想办法把这个 2^{28} 的 state 砍下来，别老惦记你那完全信息了。

• 一个自然的想法是，考虑什么方式可以把 2 的复杂度消掉。

  • 观察到 x 最多只有 \lceil\dfrac{n}{2}\rceil\lceil\dfrac{m}{2}\rceil\to 8 种，显然这个可以考虑扔在那里。

  • 于是考虑到一件事：我们手上的 o，只要“解锁”了，就没有区别，都是转移系数。所谓“解锁”，就是可以填了。

• 这就启示我们正解大概率只压了 x 的情况。我的思考就到这里，因为后面我误入歧途了，下面会是“做过之后重新看”的感觉。

• 只压 x，只压 x 是多少？2^8，就算算上枚举该填哪个数（现在 o 都成转移系数了当然不会有填到哪去的转移复杂度），也就 2^8\times 28，而 \dfrac{10^8}{2^8\times 28}\approx 13950。

• 大坑还在后面哪！这么冗余的复杂度使用，其实就是暗示我们，除非使用升维等方式，否则绝对不可做，否则没有必要数据范围这么小。

• 回过头来考虑我们的 DP。

  • 现在它大概长成 dp_{i,sta} 的样子，表示填了 1\sim i，sta 中的 x 填过了。

  • 初始化非常显然，dp_{0,0}=1。

  • 转移呢？怎么转移？

    • 填一个 x：非常简单。

    • 填一个 o：...

• 发现我们拼了老命也不过是能预处理出一类 o 的可行性，我指的是知道目前有多少个一类 o 解锁了。而二类 o 的解锁情况，几乎不可避免地指向全信息状态——

• 仔细想想，我们为什么老是关心二类 o 的解锁情况？如果没解锁就填了，会发生什么？

• 那么这个 o 会成为一个实质 x。我们构造出了比 sta 更多的 x。

• 好，那么我们考虑一下：就这么 DP 的话，我们的 DP 含义是什么？

• 我计划让 full 内为 x，当前填了 i 个数，当前 full 的子集 sta 已经是 x 了，但实际上我不知道是不是在 full 外还有 x，的总方案数。最后的 dp_{n\times m,full} 就是我的结果。

• 那翻译一下岂不就是 x 构成一个 full 的超集的方案数吗！容斥！暴力构造 full 的所有超集，然后容斥。可以证明，超集的元素规模（指二进制状态大小）也是 2^8 的，但超集大小呢？

• 暴搜发现共有 16334 种合法状态（只考虑了 x 不冲突，未考虑 x 的下界）。伏笔回收。

• 总复杂度大约 2^8\times nm\times 16334\approx 1.17\times 10^8，考虑到这是个 O，肯定足够通过本题。

P5369 [PKUSC2018] 最大前缀和

• 题意：求一个序列的所有排列的最大前缀和之和。特别地，最大前缀和对应的前缀不能为空。

• 数据范围：n\leqslant 20。

• 依赖大概是...嘿嘿。下面说。

• 首先我们非常自然地想到去算每个 sta 中的数字构成最大前缀和来源的方案数。不妨约定，把一个排列的贡献归给极长的那个和为最大前缀和的前缀。

• 容易想到直接暴力计算方案数为 ppc(sta)!\times (n-ppc(sta))! 然后容斥，需要向前容斥和向后容斥：

  • 不能有一个更短的前缀，其和大于 sum_{sta}。

  • 不能有一个更长的前缀，其和大于 sum_{sta}。

• 显然这玩意双向没法做，于是想到对 sta 按 sum 降序排序，相当于 toposort 了。发现能做，但是 3^n，除非维护带修子集和和超集和。问机房大佬，佬曰：没这种鬼科技！

• 啊哈哈...那我们来审视一下它为什么要容斥吧。

  • 向前：可以转化成 1\sim ppc(sta) 这一段不能有一段真后缀的和 <0。

  • 向后：可以转化成 ppc(sta)+1\sim n 这一段不能有一段前缀的和 \geqslant 0（记得吗？我们把贡献归给最长的了）。

• 发现每个 sta 依赖的是内部排列的合法性和补集排列的合法性，且两者相互独立。考虑怎么做这个玩意的 O(2^n\times n)\sim O(2^n\times n^2)。

• 不妨设计 DP 如下：

  • 状态设计：f_{sta},g_{sta} 分别表示 sta 的没有后缀和 <0/没有前缀和 \geqslant 0 的排列数。

  • 初始化：...可以声明说 f_0=g_0=1？这其实是不合定义的，一个更 specific 的初始化应该是 f_{2^x}=a_x\geqslant 0,g_{2^x}=a_x<0。

  • 转移：好像方式比较多，就说一下我的写法吧，是一个我在题解里看到的过分妙的转移。

    • 强制把 f_{sta} 看做是由所有 f_{sta'} 转移来的，其中 sta'\subsetneq sta 且 ppc(sta)-ppc(sta')=1，这种“转移”指的是尝试给 sta' 对应的排列前面加一个数字。

    • 于是转移式是这样的：f_{sta}=\sum f_{sta'}\times [sum_{sta}\geqslant 0]，sta' 定义见上。既然 sta' 的那些排列本身合法，那么在开头加一个数只新构造了一个长度为全长的前缀需要检验！

• 复杂度 O(2^n\times n)，善哉。

需求式问题

• 典型代表如 TSP 及泛化 TSP 和 \text{P5366 [SNOI2017] 遗失的答案} 等，两者分别是物品需求式和属性需求式的典例。

• 特点是给出 n 个物品，求满足某种需求的最小总代价/总方案数。

  • 获取尚未获取的物品的可行性和代价可能是关于当前已经获取的物品集的函数。

• 状态通常为 dp_{sta,\dots} 表示已经有了 sta 对应的物品集/性质集的最小总代价。

• 初始化为 dp_{start,\dots}=c_{start}（可能起始状态就有某些物品/性质，并强制付过了对应代价）。

• 状态转移大体分两类：

  • 压物品：dp_{sta,\dots}=\max_{j\in sta}(dp_{sta\oplus j,\dots}+w_j)。

  • 压属性：

    • 比较舒服的是顺推，dp_{i,sta}\to dp_{i+1,sta},dp_{i+1,to}，这里的 to 是原状态加入 a_{i+1} 后的结果状态。

    • 鉴于一般是逐物品枚举，无非选或不选，谈不上“优化转移复杂度”一说，所以就先不考虑很麻烦的状态转移方程了，毕竟得算除去某个物品的状态，而状态可能只满足结合性，不满足差分性。

    • 事实上，即使将转移方程写出来，转移来源也很可能是离散的，谈不上优化。

• 复杂度 O(k^n\times n^2)，其中 k 为状态的进制。辅助维开销具体问题具体分析。

P1171 售货员的难题

• 题意：求将每个点都恰访问一次后回到起点的最小总路程。几乎就是经典 TSP。

• 数据范围：n\leqslant 20。

• 需求是都恰访问一次。

• DP 设计如下：

  • 状态设计：dp_{sta,i} 表示访问过 sta 中点，停留在 i 的最小总代价。

  • 初始化：dp_{sta_s,s}=0。

  • 状态转移方程：dp_{sta,i}=\min_{j\in sta} (dp_{sta\oplus sta_i,j}+c_{j,i})。

• 复杂度 O(2^n\times n^2)。请记住 n=20 是这个复杂度的标志数据范围。

P4011 孤岛营救问题

• 题意：在一张 n\times m 的网格图中求从 S 到 T 的最短路。特别的是，有 K 把钥匙，某些边需求对应钥匙。某些边不存在。

• 数据范围：反正就是 O(nmkey\times 2^K) 的范围呗，其中 key 为关键点（钥匙或 S,T）个数。

• 需求是走到 T，钥匙是实现需求的手段。

• 暴力 bfs 预处理在有 sta 的钥匙时，从 u 到 v 的最短路长度。于是有如下 DP：

  • 状态设计：dp_{i,sta} 表示当前在 i，有 sta 的钥匙，最小总路程。

  • 初始化：dp_{S,0}=0。

  • 状态转移：直接顺推，事实上这个应该比较像拓扑排序风格。

• 足够通过本题。

P3947 肝活动

• 题意略。

• 需求是得分和都打过。

• 设计 DP 如下：

  • 状态设计：dp_{sta} 表示打完 sta 中的歌的最大得分。

    • 当前的时间是隐含在其中的。这是典型的极小状态集。

  • 初始化：dp_0=0。

  • 状态转移方程：顺推吧，无非 O(2^n\times n)。这一复杂度的标志性数据范围是 n=22。

• 足够通过本题。

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

• 题意略。

• 需求是都杀了。

• 发现每次暴力选两个构造直线然后检验的复杂度是 O(2^n\times n^3)，无法接受。

• 考虑预处理曲线。预处理复杂度 O(n^3)，将 dp 部分降到了 O(2^n\times n^2)。

• 可以进一步优化！强制钦定一定要打死编号最小的猪。于是复杂度为 O(2^n\times n)。强制顺序来将本质相同的方案的各种排列的复杂度舍去，这很妙。

P3959 [NOIP2017 提高组] 宝藏

• 题意略。

• 需求是连通。也可以说是“把所有点都装进连通块”。

• 第一眼确实很 Prim，但想一下会发现这个东西明显有后效性。

• 反正是 TSP 板子，直接 O(2^n\times m) 创过去吧！

• 更精巧的解法？考虑使用邻接矩阵。会好一些，大概是 O(2^n\times n^2)。没有什么特别的一道题。

P2322 [HNOI2006] 最短母串问题

• 题意略。从题目名称应该就能看出来。

• 需求是遍历。

• 谈一下数据范围：n\leqslant 12,|S|\leqslant 50。这给了我们一个使用比较暴力的方法的机会：

• 强行建 AC 自动机，然后一个点拆成 2^n 个点，跑 bfs（事实上有许多点是没有意义的点）。最后把所有解构造出来，排序，取字典序最小的。

• 一个小细节是 rsta_{now}=sta_{now}|sta_{fail_{now}}。

• 这种做法的主要问题是卡空间，毕竟时间只有 O(\sum \times 2^n)\approx 2.5\times 10^6。下面谈一种更优美也更优的做法。

• 对于一般的 TSP 问题，我们一旦从上一个点出发，就必然是在去下一个点的路上。在 AC 自动机上显然不是，所以我们设法规约它：

P5366 [SNOI2017] 遗失的答案

• 主体部分请参看 P5366 [SNOI2017] 遗失的答案 解题报告。

• 鉴于其是早期作品，内容缺乏公理化和规约，这里给出简述：

• 完成此步转化并都 /G 后，题目的真面目就浮现出来，即对 L 的质因数的次数的上/下界需求。

• 因为 \omega(L)\leqslant 8，所以可以直接压。至于后面的正反 DP、FMT 合并等，都是较为顺理成章的事情。

P3092 [USACO13NOV] No Change G

• 题意略。有点另类的需求式问题。

• 需求是全买的同时省钱。

• 抓住必须按顺序买物品这一点，我们可以二分转移。

• 总复杂度 O(2^n\times m\log m)，这里我把硬币数记为 n，物品数记为 m。

复合式问题

• 典型代表如 \text{P1896 [SCOI2005] 互不侵犯} 和 \text{P4460 [CQOI2018] 解锁屏幕}，分别为物品需求和属性需求的典例。

• 特点是给出 n 个物品，物品之间有一些矛盾关系，同时要求选一个物品集以满足某种物品/属性上的需求，求最小总代价或方案数，即矛盾式问题和需求式问题的复合。

• DP 设计基本是基于矛盾式或需求式来做，视情况升维。这里不详谈，看题吧。

P1896 [SCOI2005] 互不侵犯

• 题意：在 n\times n 的棋盘中放 K 个国象的国王，使他们不互相攻击，求方案数。

• 数据范围：原题 n\leqslant 9，可以做 n\leqslant 15。

  • 这里认为 1s 在正常常数下可以跑 4\times 10^8。

• 其依赖是不攻击（不存在），需求是放 K 个。

• 首先我们算一下 K。容易证明，K\leqslant \lceil\dfrac{n}{2}\rceil^2。

• 注意到王的攻击范围很狭窄，压 n\times n 显然没有必要。考虑逐行转移。

• 考虑设计 DP 如下：

  • 初始化：dp_{0,0,0}=1。

  • 状态转移：

    • 朴素转移：顺推比较好写。

      • 暴力枚举下一行的放置情况，判定合法性并转移。

      • 转移复杂度 O(2^n)，总复杂度 O(2^{2n}\times n^2\times K)。

      • 在 n=9 时 \approx 5.3\times 10^8，考虑到这种写法的转移起点必须合法，应该有足够通过的小常数。

    • FMT 优化：

      • 显然这可以用 FMT 优化求子集和，对于每个二元组 (i,j) 有 O(2^n\times n) 的复杂度，故总复杂度为 O(2^n\times n^2\times K)。

      • 在 n=15 时 \approx 4.7\times 10^8，足够通过本题。

P4460 [CQOI2018] 解锁屏幕

• 题意：给出 n 个二维平面上的点，求合法的解锁屏幕手势有多少种。一个点的有序集合 S 被称为合法的解锁屏幕手势，当且仅当：

• 数据范围：n\leqslant 20,|x|,|y|\leqslant 10^3。

• 它的依赖不能经过尚未访问过的点，需求是 ppc\geqslant 4。其实有点像 TSP。

• 故考虑暴力预处理 sta_{u,v} 表示 u,v 连线经过的点，然后做如下 DP：

  • 状态设计：dp_{sta,i} 表示经过了 sta 中的点，当前停留在 i 的总方案数。

  • 初始化：dp_{sta_i,i}=1。

  • 状态转移方程：dp_{sta,i}=\sum\limits_{j\in sta \And sta_{j,i}\in sta} dp_{sta\oplus sta_i,j}。

• 也许可以优化但我不想考虑了，O(2^n\times n^2)，足够通过本题（虽然看起来是 4\times 10^8 但显然这个复杂度溢出不少，常数足够优秀）。