dp 优化 2

· · 算法·理论

本文记录一些不是很常见的 dp 优化方法。

一些比较通用的 dp 优化方法。

qoj9700

对于一个无从优化的 dp 式子，可以考虑直接把他的生成函数列出来，在某些情况下可以方便转移，如根据其性质直接用 FFT / NTT 暴力维护或者其插值非常好维护等。

先用一遍二项式反演，然后定义 dp_{u,i,j,0/1} 表示 u 的子树内，当前钦定了 i 个点，容斥中 u 的子树大小为 j 且 u 是否被选的答案，但是这个直接做是 \mathrm O(n^4) 的。

不过你发现 i 之和卷积有关，和转移系数是无关的，所以我们考虑先不看 j 这一维，先求出插值。然后后面求的时候再把 j 的贡献算一下即可。

uoj1084

考虑我们在 u 这个点就死了的条件：

\forall v \in \text{son}(u)\\ \exist w \in T_v,(w,u) \in E

所以对于一个 k，其是否可行的条件为：

\forall u \notin S,\exist v \in \text{son}(u)\\ \forall w \in T_v,(w,u) \notin E

考虑用一个延后钦定的 trick，令 dp_{u,i} 表示节点 u 的子树中还有 i 条边需要向上连的答案。所以对于叶子结点 dp_{u,[u \notin S]} = 1。假设 a_i 个叶子节点中有 b_i 个指向了 u，那么我们考虑将条件 [\exist i,b_i = 0] 转化为 \prod [b_i \ge 0] - \prod [b_i > 0]。然后我们就有转移：

g^{\prime}_{i+a-b} \gets g_i \times dp_{v,a} \times \dbinom{a}{b}

发现 i 和 a 其实对于转移没有什么影响，所以我们考虑令：

h_{v,d} = \sum_j dp_{v,a} \dbinom{a}{d}

你发现虽然 g 可以变成正常的树形背包了，但是 h 的复杂度依然有 \mathrm O(n^3)。由于没有什么好办法，考虑写一个 OGF 出来：

\begin{aligned} F_v(x)&=\sum f_{v,i}x^i\\ H_v(x)&=\sum h_{v,i}x^i\\ &=\sum_ix^i\sum_j{j\choose i}f_{v,j}\\ &=\sum_jf_{v,j}\sum_i{j\choose i}x^i\\ &=\sum_jf_{v,j}(x+1)^j=F_v(x+1) \end{aligned}

所以在插值意义下 H_v(x) 为 F_v(x) 整体右移一位。而对于 F_u(x)，我们考虑维护其在 0,1,2,\cdots,dep_x 的值即可。

有时候暴力去求生成函数可以发现一些原本看不出的性质。这个时候就可以用这些性质做题了。

AT_abc269_h

首先我们可以设计出 dp：令 dp_{u,i} 表示 u 的子树中我们选择了 i 个节点的方案数。然后我们发现这个东西的转移是简单的：

dp^{\prime}_{u,i} \gets \sum \limits_{j + k = i} dp_{v,j} \times dp_{u,k}

然后令 dp_{u,1} = 1 就行了。但是你发现复杂度爆掉了。然后考虑从生成函数的角度来看这个 dp 式：

F_x(z) = z + \prod_{y \in \text{son}(x)} F_y(z)

观察一下这个多项式的特征：\text{deg} F_x(z) \le siz_x，所以这启示我们去做一些和子树大小有关的操作。所以考虑重链剖分。然后考虑用类似于全局平衡二叉树的方式：维护所有轻子树的多项式乘起来的结果，即令 G_x(z) = \prod \limits_{y \in \text{son}(x),y \neq \text{dson}(x)} F_y(z)。

然后对于一条重链，我们考虑优化重链上面的转移，即考虑这条重链上面选了 0/1 个点：

F_t(z) = \prod_{x \in \text{chain}} G_x(z) + z \sum_{x \in \text{chain}} \prod_{\substack{y \in \text{chain} \\{\text{dep}}_y < \text{dep}_x}} G_y(z)

然后你考虑用分治 FFT 去快速计算上面这个 F_t(z)，即返回一个 pair 分别维护当前前半部分和后半部分的多项式。所以计算 F_t(z) 可以做到 \mathrm O(n \log^3 n)。又因为轻子树的子树和在 \mathrm O(n \log n) 内，所以计算 G_x(z) 的复杂度就是 \mathrm O(n \log^3 n)，可以通过。

考虑用重链剖分+链分治来优化链上的 dp 转移。具体的，考虑先把轻子树的值先全部维护好，然后对于重链考虑用分治来加速转移。

CF1010F

考虑去令 b_u = a_u - \sum \limits_{v \in \text{son}(u)} a_v。那么我们发现题目中的条件其实就是 \forall i \in [1,n],b_i > 0 且 \sum \limits^n_{i=1} b_i = X。所以我们只需要求出大小为 i 的联通块大小的数量然后再乘上一个组合数就做完了。

然后我们考虑怎么去求大小为 i 的连通块数量：考虑令 dp_{u,i} 表示根为 u 的子树中，包含 u 的连通块大小为 i 的连通块数量，那么转移就是：

dp_{u,i} = \sum^i_{j=0} dp_{ls_u,j} \times dp_{rs_u,i - j - 1}

同时 dp_{u,0} = 1。然后你考虑和上面的那个题同样的做法，写出他的生成函数形式：

F_u(x) = xF_{ls}(x)F_{rs}(x)+1

然后你仿照上一个题去写一个链剖分即可。

QOJ 7419

当转移不是多项式乘法的时候怎么办呢？

考虑一个暴力 dp：令 dp_{u,i,0/1} 为当前在 u 的子树，匹配大小为 i，且 u 是否有匹配的方案数。然后我们就有转移：

dp_{u,i,0/1} \gets \max_{j+k=i} \{dp_{u,j,0/1} + \max(dp_{v,k,0},dp_{v,k,1})\} dp_{u,i,1} \gets \max_{j + k = i - 1} \{dp_{u,j,0} + dp_{v,k,0} \} + w(u,v)

然后你发现这个时候的转移是 (\max,+) 卷积！注意到费用流是有凸性的，所以就说明其实 f_{u,0/1} 是有凸性的，然后我们可以用于闵可夫斯基和的做法使得两个凸包 (\max,+) 卷积的复杂度变成 \mathrm O(\log (|a|+|b|))，但是因为还有 0/1 这一维，所以不能直接用差分维护，所以复杂度还是 \mathrm O(|a| + |b|)。那么现在的复杂度还是 \mathrm O(n^2)。

既然如此，我们可以考虑让一个信息被合并的尽量少次数，所以我们还是可以考虑树链剖分加上链分治即可。由于每一次算所有轻儿子的凸包合并也需要用分治来合并，所以对于一个节点，我们会对于 \mathrm O(\log n) 条不同的重链产生贡献，而对于一条重链，我们还需要一层分治。所以最后的复杂度就是 \mathrm O(n \log^2 n)。

AT_abc311_h

如果你连数组连凸性都无法保证呢？

依旧考虑设计一个暴力 dp：dp_{u,i,0/1} 表示表示以 u 为根的子树中选的节点总重量为 i，最浅的一层节点颜色为 0/1 的最大总美丽度。

然后你发现转移就是一个类似于背包的一个转移：

dp_{u,i,c} \gets dp_{u,i - j,c} + dp_{v,j,c} \\ dp_{u,i,C_u} \gets dp_{u,i - V_u,1 - C_u} + W_u

复杂度为 \mathrm O(nm^2)。然后你发现这个 dp 数组啥性质都没有，但是如果把两个背包合并变成插入一个数就可以去掉一个 m，所以我们考虑直接让 dp_v 的初始值就是 dp_u，这样子就可以省去合并这一步了。

但是你发现其实是不对的，因为你有可能会存在这一层又选了蓝色，又选了红色的情况，所以你考虑第一次只传 dp_{u,*,0}，然后这样子就可以保证新的 dp_{u,*,0} 是对的，然后第二次我们再传 dp_{u,*,1}，同理就可以保证 dp_{u,*,1} 是对的了。

但是你发现这个时候复杂度就是 \mathrm O(2^n m) 的。不过你发现第一次传入的两个数组是一样的，所以我们可以只传入一次，所以我们考虑第一次传入重儿子，这样子我们只有轻儿子需要多遍历一遍了。

然后根据一通复杂度分析，你的复杂度可以做到 \mathrm O(n^{1.59} m)。具体分析可以看本题的其他题解。这也太魔怔了。

P12444

发现上面这个题的 dp 数组直接沿用父亲的，那如果我们只有两维 dp，即没有 0/1 这一位会怎么样呢？

同样的，如果我们正常去做树上背包的话，我们的复杂度是 \mathrm O(nm^2) 的，所以我们同样考虑和上面一样的方法：把儿子节点的初始值设成父亲节点当前的 dp，然后在转移。

不过我们有一个比较优秀的写法，就是考虑把这个树拍到 dfs 序上，然后如果我们跳过这个子树，我们只需要把下标加上 siz_u 即可跳过当前子树。所以现在我们就可以做到 \mathrm O(nk) 了。

我们称这个东西为树上依赖背包。

P14471

树上依赖背包进阶。

假设 $u$ 子树内在操作一的时候被选择了 $w_u$ 个点，那么操作二在 $u$ 上的限制就是 $c_u - w_u$。此时考虑将子树看为 $dfn$ 序上的信息，设 $s_{l_u},s_{r_u}$ 分别表示在遍历 $u$ 前进行了多少次操作一，在遍历完 $u$ 的子树后进行了多少次操作一，那么我们可以得出 $w_u=s_{r_u} - s_{l_u}$。 而操作二的上界就是 $c_u - s_{r_u} + s_{l_u}$，而我们有 $c_u - s_{r_u} \ge c_u - t > 0$，所以我们可以把问题看成在 $l_u$ 处选 $[0,l_u]$ 个，在 $r_u$ 处选 $[1,c_u - s_{r_u}]$ 个。那么 dp 的时候只需要记录操作一和操作二选择了多少个，然后可以像 [苹果树](https://www.luogu.com.cn/problem/P3780) 一题一样用单调队列去转移。而假设操作二并没有选 $u$，那么可以直接无脑选最长链，而由于这个函数肯定是有凸性的，所以可以决策单调性。