本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-15 15:18:12

10.08 DP

基本知识

DP 基础

• 考虑方式：分界线（记录前一半对后一半的影响）、状态机（记录判定 / 计算过程的状态）。

• 转移：跨层转移（相当于状态机可持久化） / 分步转移 。

DP 模型（组合模式 / 表示）

DP 优化

• 最优化：单调性、凸优化等。
• 计数：容斥、代表元、取补集等。
• 构造 / 判定。

DP 维护

DP 值有特殊性，如 slope trick 等。

CF1943D2 Counting Is Fun (Hard Version)

题意

定义序列 $b$ 是好的当且仅当其可以通过若干次操作变为全 $0$，操作为选择 $l\lt r$ 进行 $[l,r]$ 区间减一。给定 $n,k,m$，要求长为 $n$ 的序列中 $a_i\in[0,m]$。求 $(k+1)^n$ 种可能的 $a$ 序列中有多少是好的，对 $m$ 取模。多组数据，$n,k\le 3000,\sum n^2\le 10^7$。

题解

令 $a_0=a_{n+1}=0$，显然若 $a_i\gt a_{i-1}+a_{i+1}$，则 $a_i$ 不可能被删空，序列一定不合法。若全满足条件，则序列一定合法，可以发现此时从左往右不断拓展，不够则新增区间，一定可以构造出合法解。

于是现在需要对 $a_i\gt a_{i-1}+a_{i+1}$ 的序列计数，容易记录最后两个值做到 $O(nk^2)$。接着观察性质，容易发现只有 $a_i\gt a_{i-1}$ 且 $a_i\gt a_{i+1}$ 的位置 $i$ 可能非法，而这些位置一定不相邻，考虑对这些位置单独转移。

具体地，当出现这种位置 $i$ 时，从 $f_{i-1,j}$ 直接转移到 $f_{i+1,t}$，带上 $a_i$ 种类数的系数 $\min(j+t,m)-\max(j,t)$。其余转移则需保证不存在这种位置，因此状态内需要记录 $[a_i\gt a_{i-1}]$。所有转移均是一段区间，只是有的与 $t$ 有关，讨论之后将一次函数贡献到 $f_{i+1},f_{i+2}$ 的区间内，使用差分和前缀和即可，总复杂度 $O(nk)$。

CF354D Transferring Pyramid

题意

给出一个金字塔，即第 $i$ 行只在前 $i$ 列有元素。可花费 $3$ 的代价覆盖单个格，也可花费 $\frac {x(x+1)}2+2$ 的代价覆盖一个高为 $x$ 的子金字塔，求将 $k$ 个格全覆盖的最小代价。$n,k\le 10^5$。

题解

显然最小代价不会超过全部单点改的 $3k$，于是 $x$ 也不会超过 $\sqrt k$ 级别。考虑对每一列 DP，设 $f_{i,j}$ 表示考虑了前 $i$ 列，第 $i$ 列上最高的三角高为 $j$ 的最小代价，第二维大小为 $O(\sqrt k)$。有 $f_{i,j}=f_{i-1,j+1}$，同时还能新开一个三角形，有 $f_{i,j}\leftarrow \min{f_{i-1}}+\frac {j(j+1)}2+2$。转移完后每个第 $i$ 列上的位置再对小于它的所有 $j$ 加上 $3$，这可以使用前缀和维护。总时间复杂度 $O(n\sqrt k)$。

P14016 ICPC 2024 Nanjing R\] 拓扑

题意

给出一棵树，对所有 $i$ 求 $p_i=i$ 的拓扑序数量。取模，$n\le 5000$。

题解

由于拓扑排序是从根到底的，考虑对此设计状态，设 $f_{u,i}$ 表示不考虑 $u$ 子树内除 $u$ 外的点时，$p_i=u$ 的拓扑序数量。由于 $u$ 子树内其他点必定在 $u$ 之后，不会改变 $u$ 的位置，答案为 $f_{u,u}\times {n-u\choose s_u-1}\times (s_u-1)!\times \prod_{v\in son_{u}} \frac{g_v}{s_v!}$，其中 $s_u$ 表示 $u$ 子树的大小，$g_u$ 表示只考虑 $u$ 子树的拓扑序数量，后面组成了多重集排列。

再考虑转移，由 $u$ 转移到 $v$ 时，考虑先用不在 $v$ 子树内的点排，设 $h_j$ 表示 $p_j=u$ 的方案数，有 $h_j=f_{u,j}\times {n-s_v-j\choose s_u-s_v-1}\times (s_u-s_v-1)!\times \prod_{t\in son_u,t\ne v}\frac{g_v}{s_v!}$，同样是多重集排列。此时有 $f_{v,i}=\sum_{j=1}^{i-1} h_j$，将 $v$ 插入对应位置即可，只要求 $u$ 在其前面。求 $h$ 只需要预处理后面一项的前后缀乘积，对 $h$ 前缀和优化即可做到 $O(n^2)$ 的复杂度。

本题启示我们按照过程设计 DP，从而设计出类似本题自根向下这种不常见的状态。

CF1608F MEX counting

题意

给出数组 $b$，求满足 $a_{i}\in[0,n],\left| c_i-b_i \right|\le k$ 的序列个数，其中 $c_i$ 为 $a$ 数组前 $i$ 个数的 MEX。$n\le 2000,k\le 50$。

题解

考虑设计状态，由于每个位置有自身的 MEX 限制，因此必定要记录 MEX，设 $f_{i,j}$ 表示考虑了前 $i$ 个数且 $c_i=j$ 的方案数。再考虑如何转移，发现 MEX 可能单次增长很多，需要关注两个 MEX 之间的数，这也是上个 MEX 之后大于 MEX 的数。于是设 $f_{i,j,c}$ 表示大于 MEX 的有 $c$ 种值已存在的方案数，为方便转移，这里不确定具体值，而是只确定有 $c$ 种。

转移时显然有 $f_{i,j,c}=(c+j)f_{i-1,j,c}+f_{i-1,j,c-1}$，后一项没有系数是由于状态定义里不确定具体值。该值在 MEX 增大时被确定，有 $f_{i,j,c}=\sum_{k\lt j} f_{i-1,k,c+j-k-1}\times\frac{(c+j-k-1)!}{c!}$，系数为 $A_{c+j-k-1}^{j-k-1}$，表示确定若干个数填充 $(k,j)$，注意这里 $a_i=k$ 是确定的。由于每个 $i$ 对应的 $j$ 在一段长不超过 $2k$ 的区间内，总状态数 $O(n^2k)$，转移复杂度 $O(k)$，总复杂度 $(n^2k^2)$，难以通过。

复杂度瓶颈在 MEX 增大的转移，注意到该式中后两维之和均为 $c+j-1$，考虑对其进行前缀和优化，设 $g_{x,y}=\sum_{j+c=x,j\le y} f_{i-1,j,c}\times c!$，则上式可变为 $g_{c+j-1}$ 的一段区间除以 $c!$，这是能 $O(1)$ 计算的。上面的前缀和数组大小为 $O(nk)$，于是总复杂度为 $O(n^2k)$，空间可以使用滚动数组优化到 $O(n^2)$ 甚至 $O(nk)$。

本题启示我们不要只对过程考虑，也可直接考虑最终的解集本身，从而发现更加优秀的状态设计方式。

10.10 DP

• 有后效性的问题

环上 DP 可钦定结尾情况断环为链。

计数 / 概率期望类 DP 可列出包含自身的转移方程，移项得到真正的转移式。

最值类转移方程，如 $f_i=\max (t_j)$，可转为限制 $f_i\ge t_j$ 并最小化 $f_i$ 的值，这和差分约束的思想相似。之后用 Bellman-Ford 等算法硬跑也行。当转移中加的值非负时也可以用 Dijkstra 进行转移。

CF713E Sonya Partymaker

题意

有一个长为 $m$ 的环，上面有 $n$ 个关键点，要求给每个关键点钦定一个方向，使得向该方向延伸 $l$ 长度后覆盖环上每个点，求 $l$ 的最小值。$n\le 10^5,m\le 10^9$。

题解

显然答案可二分，转为判断是否能用长为 $x$ 的线段全部覆盖。设相邻两点间最多隔了 $d$ 个点，答案一定在 $[\lceil\frac d2\rceil,d]$ 内，于是二分上界设为 $d-1$ 即可。设 $b_i$ 表示 $i$ 点与下个点之间隔的点数，通过平移使得 $b_n=d$，于是 $1,n$ 均不能独立覆盖 $b_n$，方便断环为链。

考虑使用 DP 解决，设 $f_i$ 表示前 $i$ 个点覆盖 $i$ 点之前所有点后，最多向后延伸的距离。初值分 $1$ 的方向讨论，若 $1$ 向前则有 $f_1=0$，此时若 $f_n+x\ge b_n$ 则 $x$ 合法；若 $1$ 向后则 $2$ 必向前，否则 $n$ 无法独立覆盖 $b_n$，于是有 $f_2=\max(0,x-b_1-1)$，此时若 $f_n+f_2\ge b_n$ 则 $x$ 合法。

转移时同样对 $i$ 的方向分讨，若 $i-1$ 可延伸到 $i$ 前则可向右，即 $f_{i-1}\ge b_{i-1}$ 时 $f_i\leftarrow x$；若 $i-1$ 和 $i$ 可拼接则拼接，即 $f_{i-1}+x\ge b_{i-1}$ 时 $f_i\leftarrow 0$；若 $i-1$ 向右延伸出来，需要 $i-2$ 和 $i$ 将它们中间的部分覆盖，即 $f_{i-2}+x\ge b_{i-2}+b_{i-1}+1$ 时 $f_i\leftarrow \max(0,x-b_{i-1}-1)$。感觉转移有点重复，但这样至少是对的，单轮复杂度线性，总复杂度 $O(n\log n+n\log V)$。

• DP 整体维护

• • 连续段

例如若干次令 $a'i=\max{j=i}^{i+k-1}a_j$ 或 $a'i=\min{j=i}^{i+k-1}a_j$，考虑维护所有值相同的连续段，并记录其相邻大小关系，则取最大值时所有比前面大的段左移 $k-1$，否则比前面小的段左移 $k-1$，若某个段被覆盖就删掉。可用堆等数据结构维护之。

• • 数据结构

若有 $O(n^2)$ 的 DP 状态 $f_{i,j}$，然而其从 $i-1$ 到 $i$ 的变化是区间修改等可维护的操作，可以直接使用数据结构维护目前的 $f_i$。

• • 观察整体过程

例如给出长为 $l$ 的串 $s$ 和其栈消除后的串 $t$，$s$ 中有部分位置不确定，对 $t$ 的每个前缀求其对应的合法 $s$ 个数。把图画出来后发现 $s$ 中确定时所有状态均整体平移，否则所有状态指向两边。于是删掉所有平移的行后只剩杨辉三角，可直接组合数计算。

[AGC017F] Zigzag

题意

有一个 $n$ 行网格，一条折线可用长为 $n$ 的数组 $x$ 表示，要求 $x_1=1$，且 $x_i$ 为 $x_{i-1}$ 或 $x_{i-1}+1$。要求选出 $m$ 条折线，另有若干 $x_{i,j}=x_{i,j-1}+c$ 的限制，求合法折线方案数。$n,m\le 20$。

题解

每条折线事实上可以用一个长为 $n-1$ 的 $01$ 串表示，于是设 $f_{i,S}$ 表示考虑了前 $i$ 条折线，第 $i$ 条折线为 $S$ 的方案数，复杂度至少是 $O(4^nm)$。考虑转化为向 $m$ 行 $(n-1)$ 列的网格内填入 $01$，某些格的取值有限制，且要求每行做前缀和后每列不降。

由此可设计轮廓线 DP，设 $f_{i,j,S,p}$ 表示考虑到 $(i,j)$ 位置，轮廓线上的状态为 $S$，且 $(i-1)$ 行前 $j$ 个的和为 $p$ 的方案数，转移是 $O(1)$ 的，于是复杂度为 $O(2^nn^2m)$。考虑避免对 $p$ 额外开一维状态，若在填第 $i$ 行，则每出现一次 $a_{i,j}=1,a_{i-1,j}=0$，后面就可以出现一次 $a_{i,j}=0,a_{i-1,j}=1$，即只有之前领先才能在该列少走。

于是令 $S$ 的含义变为前 $j$ 个表示第 $i$ 行的情况，后面表示之后填到该位置是否能填 $0$，为 $1$ 则不能填 $0$。每次上一行为 $0$ 且该行填 $1$ 时，将后面最近的 $1$ 改为 $0$，表示可以在此处填 $0$ 了。之后若在这种位置填 $0$，则可以消掉贡献；否则又满足修改的限制，会将下一个 $1$ 改为 $0$，于是这样的正确性有保证，时间复杂度降为 $O(2^nnm)$。

本题启示我们要关注整体变化过程，从而设计状态。

• • 方案点集

将所有可达状态放到坐标系中，只保留没被偏序的点。如果是凸的则可以使用闵可夫斯基和或 slope trick 等进行维护。

• 插值

当 $n$ 很大，需要分讨但每种的答案均为低次多项式时，可枚举足够大的若干个 $n$ ，暴力计算 $y$ 值后插值计算出一个低次多项式，再代入 $n$ 求解。

或者 DP 状态数不太多，但存在背包转移且转移次数较多时，可先去掉背包维状态改为多项式，之后带入状态数个 $x$ 只维护多项式的点值，最后再插值出结果。

10.10 思考题 大鱼吃小鱼

鸽了。整个部分大概都需要观察到极长可吃区间是 $\mathcal O(n)$ 级别的，之后应该会做。

[ARC189D] Takahashi is Slime

P9530 [JOISC 2022] 鱼 2

U477940 大鱼吃小鱼

10.12 凸优化

查看 $(p,q)$ 点和直线 $y=kx+b$，相当于 $(k,-b)$ 点和直线 $y=kp-q$，这是半平面交和凸包的对偶关系。

斜率优化的双线性型一定满足四边形不等式，于是具有凸性。

一般来说带凸性的 DP，每个位置的最优决策点单调变化。

• 凸性证明 1：考虑答案结构，用闵可夫斯基和归纳出其凸性。

U72600 【模板】wqs二分1

题意

给出正整数序列 $a$，每段的代价定义为区间和的平方，划分的代价定义为每段代价的和，求将其划分为 $k$ 段的最小代价。

题解（凸性证明 2）

当且仅当 $\frac {f(x-1)+f(x+1)}2\ge f(x)$ 时函数是凸的。于是考虑将 $x-1,x+1$ 的最优解拼起来，再转化成 $x$ 段的一个解，从而证明其不优于 $x$ 段的最优解 $f(x)$。

考虑找到分界线 $p$，使得将后一半交换后两个解均为 $x$ 段。由于 $p=0$ 时差为 $2$，$p=n$ 时差为 $-2$，且段数差连续变化，根据介值定理一定存在差为 $0$ 的时刻，于是可以变成两个 $x$ 段的解。

由于要证明大小关系，考虑找到一个和 $f'$ 使得 $f(x-1)+f(x+1)\ge f'$，从而可用 $f(x)$ 定义得到 $\frac {f'}2\le f(x)$，证明上面的式子。由于该代价满足四边形不等式，因此只要找出使得上下存在包含关系的分界点 $p$ 即可。由于差连续变化，一定存在连续的 $-1,0,1$，将 $p$ 取在此处即为包含关系，此时上式由于四边形不等式成立，于是证明了 $\frac {f(x-1)+f(x+1)}2\ge f(x)$，从而说明该函数具有凸性。

至于四边形不等式的证明，考虑 $a\lt b\lt c\lt d$，要证 $(s_d-s_{a-1})^2+(s_c-s_{b-1})^2\ge (s_c-s_{a-1})^2+(s_d-s_{b-1})^2$，拆括号化简之后得到 $-2(s_ds_{a-1}+s_cs_{b-1})\ge -2(s_cs_{a-1}+s_ds_{b-1})$，由于 $s$ 不降，根据排序不等式即可证明该结论。

• 引理：当段数权值满足四边形不等式，则最优解关于段数是凸的。证明同上。

P2619 [国家集训队] Tree I

题意

求 $n$ 点 $m$ 边的图包含 $k$ 条白边的最小生成树。

题解（凸性证明 3）

考虑证明函数上每个点均能被切到，则需证明斜率 $k$ 变化过程中，方案的段数是连续变化的。更进一步地，在本题中对于一个斜率 $k$，需要证明可能为最优的白边数量是一个连续段。根据各种调整可以证明该结论，我不会此处略去。

上面两题都满足答案 $f(k)$ 关于 $k$ 是凸的，可使用 wqs 二分求解，复杂度 $O(T\log V)$，其中 $T$ 为单轮复杂度，两题分别为 $O(n)$ 和 $O(m\lpha(n))$。

• 凸性证明 4：反悔贪心问题每次选择不如之前优，于是差分数组单调，天然具有凸性，比如模拟费用流。

LOJ6914. 爱上火车

凸优化，感觉过于难了，遂弃之。