dp 优化

sqrtqwq · 2025-09-14 19:37:27 · 算法·理论

这是有必要的。像这种比较板子的东西总结一下会好很多。

dp 优化。本文约 13k 字。

\text{Part 1.} 单调队列优化 dp

\text{Part 1.1.} 一般形式

dp 的式子一般可以写成：

dp_i = \max \limits_{j \in [l_i,i - 1]} \{dp_j + A_j\} + B_i

其中 l_i 是单调不降，此时我们就可以用单调队列去优化 dp。具体步骤为：

将所有已经处理过的 dp_j + A_j 加入单调队列。
假如队首不在 [l_i,i-1] 之中则将其弹出队列。
拿队首更新 dp_i。

注意到方程式中的 A_j 之和 j 有关，B_i 之和 i 有关。

\text{Part 1.2.} 单调队列优化多重背包

如果只看上面的式子，肯定会有人认为线段树可以代替单调队列优化 dp，但是实际上并非如此。

你有 n 个物品，每个物品重量为 w_i，价值为 v_i，数量为 k_i。你有一个承重上限为 W 的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。

定义 dp_{i,j} 表示前 i 个物品装入承重为 j 的背包的最大价值，朴素的转移方程为：

dp_{i,j} = \max \limits_{k=0}^{k_i} \{dp_{i-1,j-k \times w_i} + v_i \times k\}

那么时间复杂度为 \mathrm O(W \sum k_i)。

考虑设 g_{x,y} = dp_{i,x \times w_i + y},g^{\prime}_{x,y} = dp_{i - 1,x \times w_i + y}，其中 0 \le y < w_i，那么这个方程就可以表示成：

g_{x,y} = \max \limits_{k=0}^{k_i} (g^{\prime}_{x-k,y} + v_k \times k)

考虑设 G_{x,y} = g^{\prime}_{x,y} - v_i \times x，则方程可以表示为：

g_{x,y} = \max \limits_{k=0}^{k_i} (G_{x - k,y}) + v_i \times x

从这个例子可以看出，单调队列优化 dp 可以优化任何维度的 dp，这一点是线段树或者其他数据结构无法做到的。 ## $\text{Part 2.}$ 斜率优化 ### $\text{Part 2.1.}$ 简单情况假如对于一个 $dp_i$，若其转移式可以被写为： $$ dp_i = \max / \min \{dp_j + cost_i + cost_j + F_i \times F_j\} $$ 则其可以是用斜率优化。**下面以取 $\min$ 为例** 具体的，考虑将 dp 式子改写为： $$ dp_j + cost_j = F_i \times F_j + (dp_i - cost_i) $$ 那么此时考虑设 $y = dp_j + cost_j,k = F_i,x = F_j,b = dp_i - cost_i$。此时的转移式就变为了 $y = kx + b$ 的形式，而此时我们要找到的就是最小的 $b$。那么现在问题就转变为了找到一个点 $(x,y)$ 使得经过这个点的斜率为 $k$ 的直线在 $y$ 轴上的截距最小。那么此时考虑讲一个条斜率为 $k$ 的直线从 $y = -\infty$ 处向上移，此时碰到的第一个点就是我们要的最优点。算完之后我们再将 $(F_j,dp_j + cost_j)$ 加入决策点集当中。那么现在我们就是要快速求出第一个碰到的点和快速维护这个点集。注意到我们这个决策点一定是在下凸包上，那么考虑使用单调栈维护凸包。对于新加入的一个点，我们只需要更新凸包就行了。而对于查询第一个碰到的点我们可以直接二分求出。 ### $\text{Part 2.2.}$ 普遍情况假如我们不满足加入的 $x$ 有序，即我们每一次加入的 $x$ 不一定会添加在这个凸包的末尾，那么此时单调栈就无法胜任了，我们需要考虑使用更加通用的方式。我们发现这个凸包在任何位置都是有可能变动的，所以我们有以下两种方案： 1. 动态维护凸包。 2. 离线。动态维护凸包据说需要平衡树，不会。考虑离线怎么做，容易想到 CDQ 分治。具体的，考虑现在已经分治到了区间 $[l,r]$，那么我们现将 $i \in [l,mid]$ 的 $dp_i$ 的所有值全部算出。然后考虑对于 $i \in [l,mid]$ 建出一个下凸包，然后考虑用目前这个下凸包去更新 $i \in [mid + 1,r]$ 中的 $dp_i$。然后将其扔掉，随后递归 $[mid + 1,r]$。在这个过程中，我们的 $[l,mid]$ 所构成的凸包是不会变的，所以我们可以用二分 + 单调队列轻松维护他。 ### $\text{Part 2.3.}$ 换个角度思考？此时考虑设 $y = dp_i - cost_i,k = F_j,x = F_i,b = dp_j + cost_j$。那么我们就可以用 $(k,b)$ 来描述一根直线。然后此时我们的转移就相当于给定一个 $x$ 求最小的 $y$ 在哪里。那么现在就等于我们要维护若干条线段的最小值，这种东西我们可以考虑使用李超线段树去维护这些线段。而用这种方法我们可以支持动态的插入。那么两种方法的不同之处在哪里呢？很明显我们要维护的形式不一样，使用单调队列 + 二分维护下凸包是维护 $\min y-kx$ 而这张方法维护的是 $\min kx+b$。这两者不要搞混淆了。 ## $\text{Part 3.}$ 决策单调性 ### $\text{Part 3.1.}$ 四边形不等式优化 dp 假设 $dp_j$ 会从 $dp_i + w(i,j)$ 转移而来，同时 $w(i,j)$ 拥有四边形不等式，则 $dp$ 具有决策单调性。四边形不等式，即对于 $a,b,c,d$ 我们有 $w(a,d) + w(b,c) \ge w(a,c) + w(b,d)$。我们考虑去维护一个单调队列，这个单调队列中的每一个元素形如 $(l,r,p)$ 表示 $[l,r]$ 的最有决策点为 $p$。假如我们现在要假如一个新的决策点 $k$，那么需要经过一下流程： - 和队尾 $(l,n,p)$ 进行比较，假如 $k$ 在 $l$ 上的决策比 $p$ 还要优秀，那么就把 $p$ 弹出。 - 然后一直重复以上的操作，直到找到一个决策 $(l,r,p)$ 是 $k$ 无法代替的，那么我们就考虑用二分去求出两个决策的决策分界点，然后再把 $k$ 弹入栈中即可。那么我们的复杂度就是 $\mathrm O(n \log n)$。 ### $\text{Part 3.2}$ 离线决策单调性假设我们下载有转移式： $$ f_j \gets g_i+w(i,j) $$ 其中 $w(i,j)$ 满足决策单调性。我们考虑用分治去优化它。对于当前区间 $[l,r]$，我们考虑暴力求出 $mid$ 处的决策点 $p_{mid}$。假设当前区间 $[l,r]$ 的决策点在 $[ql,qr]$ 之间，则区间 $[l,mid]$ 的决策区间就在 $[ql,p_{mid}]$，区间 $[mid + 1,r]$ 的决策区间就在 $[p_{mid},qr]$，然后递归下去即可。时间复杂度为 $\mathrm O(n \log n)$。而 $\text{Part 3.1.}$ 的那个式子 $dp_i \gets dp_j + w(i,j)$ 就无法离线了，应为我们需要边更新 $dp$ 边计算后面的 $dp$ 值，所以我们只能用在线的方法。 ### $\text{Part 3.3}$ 如何解决 $w(i,j)$ 计算很慢的问题？注意到一个问题，我们前面都没有管计算 $w(i,j)$ 所需要的复杂度，而 $w(i,j)$ 有 $\mathrm O(n^2)$ 对，直接预处理又不现实，那么怎么办呢？假如我们无法快速地算出 $w(i,j)$，但是若 $l \to r$ 的贡献能够在 $\mathrm O(v)$ 的时间内拓展到 $(l \pm 1) \to (r \pm 1)$。由于你对于每一层的分治，你指针至多只会跳动 $\mathrm O(n)$ 次，所以用决策单调性依然是 $\mathrm O(nv\log n)$ 的。 ### $\text{Part 3.4.}$ 限定区间个数分拆问题假设你现在必须将原数组分成恰好 $k$ 段。那么先考虑朴素 dp，定义 $dp_{i,j}$ 表示目前考虑了 $[1,i]$ 分了 $j$ 段。那么我们就有两种转移： 1. 先枚举 $i$ 和转移点 $j$，然后再枚举 $k$。 2. 先枚举 $k$，然后再枚举 $i$ 和转移点 $j$。我们发现如果使用第一种转移，我们进行一次分治就会使得整个 dp 数组更改。所以考虑使用第二种转移。对于第 $k$ 层的转移，我们调用的函数为 $\text{solve}(k,n,k - 1,n)$，这是因为我们无法将前 $k - 1$ 个数分成 $k$ 段，所以我们也不能从 $k-2$ 转移了。然后这个复杂度就是 $\mathrm O(nk\log n)$ 了。假如不限定区间个数的话，直接套一层 CDQ 分治即可按照顺序完成转移。 ## $\text{Part 4. Slope trick}

Slope trick 一般用于维护二维 dp，把第一位看成看成自变量，其余的维度看成函数，这个函数有如下的性质：

是分段一次函数。
是凸的，并且每一段斜率较小并且为整数。

在 Slope trick 当中，我们一般维护某一个 x_0 处的 f(x_0),k_0 以及函数每个斜率变化点的集合。具体的，假如在位置 x，斜率增加了 \Delta k，那么就在集合当中插入 \Delta k 个 x。

而 Slope trick 可以支持我们快速维护很多操作：

相加：f(x_0),k_0 直接加，斜率变化点的集合直接合并。
取前缀 / 后缀 \min / \max：以前缀 \min 为例，将水平区间后面的变化点去掉。
求全局 \operatorname{arg \min}：提取 k=0 部分。
平移或反转：维护 f(x_0),k_0 的变化，然后全局打标记。

\text{Part 5.} wqs 二分

wqs 二分通常用于解决有限制选取个数的 dp 问题。且这个 dp 是凸的。

一般来说，如果我们没有这一个条件，我们能很快的得出答案。

如果正常 dp 我们发现我们的状态有可能是 \mathrm O(nk) 的，我们无法知道这整一个 dp 的样子，所以此时我们考虑用一个斜率为 k 的直线 l_k 来不断切这个 dp 函数所构成的图像，然后来寻找最大值。

那么对于一条直线 l_k 我们的任务就是去切这一个凸包上的点，使得他的截距最大。假设我们现在切的位置在 (x,dp_x)，那么此时的截距为 g_x = dp_x - kx。那么我们就变为了要求出最大的 g_x。

我们发现 g_x 实际上就是将选出来的 x 个数的权值再减去一个 k，那么我们全局减一个 k 然后取出 x 个最大值实际上就是 dp_x - kx 了，而这个是简单的，那么我们就顺利的解决了这个问题。

\text{Part 6.} 拉格朗日插值优化 dp

当你的 dp 数组的状态是一个多项式且转移方式类似于卷积，那么我们可以考虑使用拉格朗日插值来优化 dp。然后把所有的 (i,dp_i) 扔到拉格朗日插值里面然后把多项式求出来然后直接算答案即可。下面讲一下如何求出这个多项式。

设第 i 个点 P_i(x_i,y_i) 在 x 轴上的投影为 P^{\prime}_i(x_i,0)。

那么考虑构造一个函数 f_x(i) 经过点 \begin{cases} P_i(x_i,y_i) \\ P^{\prime}_{j}(x_j,0) & j\neq i \\\end{cases}。

那么我们最终求的函数 f(x) 则为 \sum^n_{i=1} f_i(x)。

Proof: 当 x = x_1 的时候 f(x_1) = y_1 + \sum^n_{i = 2} 0 = y_1，当 x = x_2 的时候 f(x_2) = 0 + y_2 + \sum^n_{i=3}0 = y_2。依此类推。

那么此时我们的问题就变成了如何构造一个 f_i(x)。

根据初中的因式定理即当 f_i(x_j) = 0 时，f_i(x) 必定包含 (x - x_j) 这一个因式。所以我们考虑将 f_i(x) 表示为 a \prod_{j \neq i}^n (x - x_j)。

那么此时考虑将点 P_i(x_i,y_i) 带入 f_i(x) 得：

a = \dfrac{y_i}{\prod^n_{j \neq i} (x_i - x_j)}

将 a 带回原式得：

f_i(x) = y_i \prod^n_{j \neq i} \dfrac{x - x_j}{x_i - x_j}

既然已经有了所有的 f_i(x) 了，f(x) 就是 \sum^n_{i = 1} y_i \prod^n_{j \neq i} \dfrac{x - x_j}{x_i - x_j}。

\text{Part 7.} 数据结构优化 dp

这种比较常见，一般用于优化一维的 dp，具体问题需要具体去考虑我们需要维护什么值。

但是这种题不一定全部都是套板子，需要具体问题具体分析。

\text{Part 8.} 例题

嘟嘟哒。

\text{Part 8.1. P4383}

定义 dp_{u,x,0/1/2} 分别表示假设当前处理到了节点 u，以 u 为根的子树内有 x 条不相交的链，u 自己为一条链/u 接在一个儿子的链上/u 不在链上的最大边权和。

假设我们目前便利到了节点 u 的儿子节点 v，那么我们就有转移方程：

dp_{u,x,0} = \max(dp_{u,x - y,0} + \max_{tpye \in \{0,1,2\}}\{dp_{v,y,type}\},dp_{u,x,0}) \\ dp_{u,x,1} = \max(dp_{u,x - y,1} + \max_{0 \le type \le 2}\{dp_{v,y,type}\},dp_{u,x - y + 1,0} + \max_{0 \le tpye \le 1}\{dp_{v,y,type}\} + w(u,v),dp_{u,x,1})\\ dp_{u,x,2} = \max(dp_{u,x - y,2} + \max_{0 \le type \le 2}\{dp_{v,y,type}\},dp_{u,x - y + 1,1} + \max_{0 \le tpye \le 1}\{dp_{v,y,type}\} + w(u,v),dp_{u,x,2})

直接做是 \mathrm O(nk) 的。注意到我们 dp 数组是凸的，而且是强制选 k 个，所以说考虑使用 \text{wqs} 二分。

那么我们考虑设 dp_{u,0/1/2} 表示 u 的状态分别为 0/1/2 时的最大边权和，而我们发现如果只记录这个 dp 数组无法转移，所以考虑在记录一个 g_{u,0/1/2} 表示三种情况最大值所选的边的数量，那么此时我们就有转移式：

dp_{u,0} = \max(dp_{u,0} + \max_{tpye \in \{0,1,2\}}\{dp_{v,type}\},dp_{u,0}) \\ dp_{u,1} = \max(dp_{u,1} + \max_{0 \le type \le 2}\{dp_{v,type}\},dp_{u,0} + \max_{0 \le tpye \le 1}\{dp_{v,type}\} + w(u,v),dp_{u,1})\\ dp_{u,2} = \max(dp_{u,2} + \max_{0 \le type \le 2}\{dp_{v,type}\},dp_{u,1} + \max_{0 \le tpye \le 1}\{dp_{v,type}\} + w(u,v),dp_{u,x,2})

那么我们的 g 跟着 dp 的转移方式转移即可。

\text{Part 8.2 CF802O}

注意到是一个强制选 k 个的问题，所以考虑用 \text{wqs} 二分。

我们来考虑 check 怎么写。

每次我们往堆中加入 a_i，然后再考虑怎么配对 b_i。

那么有如下两种情况：

和之前最小的 a_x 配对，代价为 a_x + b_i。
拆散原本的一对配对，然后再组合，那么代价就是 (a_x + b_i) - (a_x - b_y) = -b_y + b_i。

然后拿一个小根堆维护匹配的情况即可。有没有匹配的 a_i 都要 push 进去。

\text{Part 8.3. ARC070E}

先有个朴素的 dp：我们定义 dp_{i,j} 表示把第 i 个方块移到 j 这个位置上的最小代价。那么转移方程就是：

dp_{i,j} = |j - l_i| + \min_{j - len_{i - 1} \le k \le j + len_i} dp_{i - 1,k}

然后因为 |j - l_i| 为凸函数，然后我们发现 dp_{i,*} 为凸函数。然后我们考虑用队列来维护这个凸包的每一个转折点。

具体的，我们维护斜率大于 0 和斜率小于 0 的部分的转折点，同时答案必定会在斜率等于 0 时取到。

\text{Part 8.4. CF1830F}

数据结构优化 dp。

考虑 dp。我们定义 dp_i 为我们最后一个激活的点为 i 的最大权值，但是其中不包括 i 的贡献。

应为我们不会算当前点的贡献，所以我们可以增加一个虚点 m + 1，那么答案就是 dp_{m + 1}。

转移就是我们枚举下一个激活的点的位置。因为我们现在加的是 i 对于答案的贡献，那么我们就有：

dp_j = \max(dp_j,dp_i + \sum_{l = 1}^n \sum_{r = 1}^n [l \le i \le r < j] \times p_i)

然后扫描线一下，对于所有的 x 维护所有 y 的贡献，最后取 \max 即可。

接着我们发现贡献的式子是一个一次函数 y_i = k_i x_i + b_i。那么我们需要维护三种操作：

全局求 \max(y_i)。
对于一个区间 [l,r]，让里面的所有 x_i 都加上 1。
单点修改 b_i。

我们用 KTT 来维护这些一次函数，时间复杂度为 \mathrm O(m \log^3 m)。

\text{Part 8.5. P4463}

考虑定义 f(i,j) 表示前 i 个数值域在 [1,j] 的方案数，那么我们就有：

f(i,j) = f(i - 1,j - 1) \times j + f(i,j - 1)

则答案 ans = f(n,k) \times n!，但是直接这么做是 \mathrm O(nk) 的，所以考虑优化。此时我们敏锐的发现 f(n,j) 是一个关于 j 的 2n + 1 次多项式。那么我们可以直接跑出 j \le 2n + 1 的 f 值然后直接拉格朗日插值吧这个多项式求出来然后再把 k 带进去即可。

\text{Part 8.6. P3642}

太牛太神仙。

设 dp_{u,x} 表示以 u 为根节点的子树中结束时间统一为 x 的最小代价，那么我们有转移式：

dp_{u,x} = \sum \min_{y \le x} \{dp_{v,y} + |w - x + y|\}

直接这么转移是 \mathrm O(n(\sum w)^2) 的。接下来，我们考虑把 dp_u 的所有点值写成函数的形式 dp_{u}(x)。然后考虑 dp_{v}(y) 对父亲 dp_{u}(x) 的贡献。此时我们发现 dp_u 是一个下凸函数，且斜率均为整数。那么 dp_v(y) 的最优取值就是斜率为 0 的一段，我们记这一段为 [L,R]。同时记 F_v(x) 表示 dp_v 对于 dp_u(x) 的贡献，w 为 u \to v 的边权。此时我们就有 F_v(x) = \min_{y \le x} \{dp_{v}(y) + |w - x + y|\}。

接下来对于 x 分类讨论：

那么 F_v 对于 dp_v 的变化关系就是：

由于斜率均为整数所以考虑使用 \text{Slope trick}。又由于两边的拐点是单调下降的，所以考虑用可并堆来两边的拐点。可并堆可以直接使用左偏树实现。

\text{Part 8.7. P12074}

发现问题可以转化为：

有 n 个栈，依次按顺序处理 m 个数，对于每个数我们可以任选一个栈把栈里所有的数符号取反，并把当前数压入栈中。

发现正着做涉及对之前的数符号的更改，不好做。所以考虑倒着做，就不再涉及符号的更改，此时我们只需要只要考虑当前数符号是否改变，缺未取反的数个数减去取反的数的个数在 [0,n] 范围内即可。那么我们考虑设 dp_{i,j} 表示后 i 个数中，取反的数减掉未取反的数的个数为 j，那那么我们就有：

dp_{i,0} = dp_{i - 1,1} - a_i\\ dp_{i,n} = dp_{i - 1,n - 1} + a_i\\ dp_{i,j} = \max(dp_{i - 1,j - 1} + a_i,dp_{i - 1,j + 1} - a_i) \ \ \ \ j \in[1,n)

同样的我们考虑把 dp_i 的所有点值写成函数的形式 dp_{i}(j)，而 dp_{i}(j) 是一个关于 j 的上凸包，而这个转移实际上就是 dp_{i - 1} 与一个点数为 2 的凸包作闵可夫斯基和。同时注意到这个上凸包的所有斜率都是正整数，所以直接用 \text{Slope trick} 就可以了。

\text{Part 8.8. ARC066D}

先考虑没有修改的情况。

定义 f_i 表示 [1,i] 之间贡献最大值，同时定义 s_i = \sum_{j=1}^i T_i。那么我们就有转移：

f_i = f_j + \dfrac{(i - j)(i - j + 1)}{2} - (s_i - s_j) \\ f_i + s_i - \frac{1}{2}i^2 - \frac{1}{2}i = -ij + f_j + s_j + \frac{1}{2} j^2 - \frac{1}{2}j

然后发现是一个斜率优化的形式，所以可以 \mathrm O(n) 直接求出。

如果有修改，那么我们再定义一个 g_i,h_i 分别表示 [i,n] 的贡献的最大值，钦定需要选择 i 的最大值，那么答案就为 \max(f_i + g_i,h_i - (X_i - T_{p_i}))。g_i 的处理方式和 f_i 一样，接下来考虑如何计算 h_i。

首先有一个 \mathrm O(n^2) 的转移式子：

h_i = \max_{l < i < r}\{f_l + g_r + \frac{(r - l)(r - l + 1)}{2} - s_{r - 1} + s_l\}

然后直接用 CDQ 求优化这个式子即可，具体可以看 \text{Part 2.2}，这里是类似的。这里给一个 code：

if(l == r)return ;
    int mid = l + r >> 1,tot = 0,mx = -1e18;top = 0;
    for(int i = mid + 1;i <= r;i++)c[++tot] = Point(i,g[i] + i * (i - 1) / 2 - sum[i - 1]);
    for(int i = 1;i <= tot;i++)
    {
        while(top > 1 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) <= 0)top--;
        stk[++top] = i;
    }
    for(int i = l,j = top;i <= mid;i++)
    {
        while(j > 1 && (c[stk[j]].y - c[stk[j - 1]].y) <= (c[stk[j]].x - c[stk[j - 1]].x) * i)j--;
        int k = stk[j] + mid;h[i] = max(h[i],mx);mx = max(mx,f[i] + g[k] + (k - i) * (k - i - 1) / 2 - sum[k - 1] + sum[i]);
    }
    tot = top = 0;
    for(int i = l;i <= mid;i++)c[++tot] = Point(i,f[i] + i * (i + 1) / 2 + sum[i]);
    for(int i = 1;i <= tot;i++)
    {
        while(top > 1 && (c[i] - c[stk[top - 1]]) * (c[stk[top]] - c[stk[top - 1]]) <= 0)top--;
        stk[++top] = i;
    }
    mx = -1e18;
    for (int i = r,j = 1;i > mid;i--)
    {
        while(j < top && (c[stk[j + 1]].y - c[stk[j]].y) >= (c[stk[j + 1]].x - c[stk[j]].x) * i)j++;
        int k = stk[j] + l - 1;h[i] = max(h[i],mx);mx = max(mx,f[k] + g[i] + (i - k) * (i - k - 1) / 2 - sum[i - 1] + sum[k]);
    }
    solve(l,mid);solve(mid + 1,r);

\text{Part 9.} 练习题

P5633
P3515
P9338
P11598
P10181
P8544
P9266
P5896
P4983
P6246
P1912
P4272
P3571
P3643
P8290