与[NOI2022] 移除石子有关的dp技巧总结

· · 个人记录

插头

在插头 DP 中有插头这个概念。

该题用状压的方式存储了轮廓线上的每条边能否与相邻格子连接。

有些题决策之间会互相影响，此时就可以设计类插头。

形式化的，有若干要求形如只有在第 j 个位置执行决策 b，才能在第 i 个位置执行决策 a（i<j）。此时，就可以在执行完决策 a 后将其存到状态里。等到执行决策 b 时判断状态里是否有决策 a 已经执行过的信息，如果有就强制执行决策 b。

下面给出几道例题，以设计插头的角度去思考：

Neko Rules the Catniverse (Large Version)

不允许重复，根据经典套路枚举值域。

每次插入一个数，这个数只能插在不小于这个数减 m 的位置。

此时，前面的决策就会影响到后面的决策，考虑把前面对后面会产生影响的决策塞到状态里。

由于 m 比较小，可以直接状压当前枚举的值减 i 这个数是否存在。

最后矩阵快速幂优化以下就行了。

Bear and Cavalry

首先将两个数组分别排序后配对的两个数就不会太远。

由于不能重复匹配，所以转移的时候我们要知道有哪些格子还可以用。

由于转移的时候可能会占掉后面的格子，所以前面对后面产生了影响。

于是直接可以将一个格子是否被占用设计成类插头，直接状压，动态 dp 即可。

Gerald and Path

从左往右 dp，在一个点考虑这里的线段往哪个方向延伸。

如果往左延伸则可能会重合。

考虑贡献提前计算，到达一个格子时直接考虑这个格子是否要贡献到答案。

如果这个格子需要贡献到答案，则后面就必须有一个往左延伸到这个位置的线段。

这就类似本文开头的那个模型，设计类插头为当前有哪些格子需要被延伸。

直接这么设计状态量很大，不过可以发现我们只关心需要被延伸到的最靠左的格子，所以直接开一维记录这个格子在哪即可。

对于往右延伸的情况，同样是前面对后面产生影响。把影响记录到状态里，也就是记录当前已经延伸到的最靠右的位置是什么。

于是这就是个三维的 dp 了。

[NOI2023] 桂花树 也用到了此技巧，这里不再赘述。

搜状态

有的题看似状态是指数级别的，但一搜可以发现本质不同的状态数是很少的，就可以以此为出发点进行 dp。

[SDOI2013] 淘金

首先可以发现 f(x) 的答案的种类数不多。写个爆搜可以发现答案的种类只有不超过 10^4 种。

直接枚举 f(x) 的值就能乱做了。

Around the World

注意到值域很小，但是如果直接状压每个值是否存在依然不行。

只有异或操作，考虑线性基。

可以看出来本质不同的线性基个数是很少的，搜以下发现不到 400 个，于是可以把线性基的编号塞到状态里 dp。

dp 套 dp

考虑这样一个问题：

有一个长度为 n 的序列，求进行一系列决策后，代价的最小值。

假设这个问题可以通过简单的 dp 解决。

现在已知第 i 个数的范围为 [l_i,r_i]，求所有可能的情况中，有多少种情况的答案不大于 k。

此问题就可以使用 dp 套 dp 解决。

顾名思义，就是把一整个 dp 数组塞到状态里。

由于这么做复杂度是很高的，一般需要结合搜状态。

Minimal Subset Difference

首先考虑怎么求 f(x)。

用 g_{n,m} 表示考虑前 n 位，能否得到 m 这个数。

显然可以 bitset 优化。

然后搜一下发现本质不同的 bitset 只有不超过 3\times 10^4 个。

于是可以把数组 g 压到状态里，然后跑数位 dp。

实现的时候可以先预处理出来转移图。

[NOI2022] 移除石子

它来了。

l_i=r_i,k=0

把操作转化一下。

第二个操作区间长度不小于 3 等价于区间长度 3 或 4 或 5。

相当于要求若干次操作 2，使得每个数都不为 1。

前面的操作会对后面产生影响，可以设计一个类插头，存储一个每个位置已经被执行了几次操作 2。

搜一下可以发现状态量不到 20。

用 f_{n,S} 表示考虑前 n 个数，当前插头编号为 S 是否可行。

直接 dp 能通过此部分分。

l_i=r_i,k\neq0

类似的，设计 f_{n,S,k} 表示前 n 个数，状态为 S，已经添加了 k 个石子是否可行。

把表打出来可以发现 k 增大并不会使本来可行的答案变得不可行。

于是可以把状态优化到两维，用 f_{n,S} 表示前 n 个数，状态为 S，至少添加几个石子才能合法。

实际上不优化状态应该也能做，因为本质不同的状态数不变，但是会麻烦一些。

r_i\le 10

考虑 dp 套 dp，搜一下状态发现只有约 10^4 种。

预处理出来转移图直接跑即可。

r_i\le 10^9

可以发现当 r_i 很大的时候对答案是没有影响的。

所以只需要枚举到 3。

总复杂度 O(nS)。

总结

[NOI2022]移除石子在场上只有极少数的选手通过，但是在熟悉以上技巧后，推出正解还是比较自然的，并没有什么非常神仙的结论或性质。

是一道 dp 进阶的好题。