转存的 【学员分享】动态dp

先给大家道个歉： - 讲课人昨天感冒了，因此嗓子哑了，声音听起来有点不舒服 - 讲课人不会在 ppt 里插入 $\LaTeX$，因此选择了直接在 typora 里写好再截图到 ppt 里 的下策， 如果有需要的话，可以和我要 .md 文件 - 树上动态 dp 可以使用 “全局平衡二叉树” 做到 $1\log$，但是讲课人才疏学浅，只会树剖 $2\log$ 做法， 因此这个 ppt 中也只会介绍树剖做法 - 讲课人只是一个萌萌小朋友，如果哪里讲错了，还麻烦大佬指出 前置知识： - 线段树 - 既然是 “动态” 的 dp，那么肯定要支持修改操作 - 大家在上周的学习中已经学过了线段树，这里就不再赘述 - 矩阵乘法 - 本质其实是 dp 的转移过程 - 不会的同学可以去看一下 洛谷日报#108 https://shehuizhuyihao.blog.luogu.org/post-zhen-sheng-fa SP1043 GSS1 - Can you answer these queries I 题意简述：给出长度为 $n$ 的序列 $a$ 以及 $m$ 组询问，对每组询问 $[l_i,r_i]$ 回答区间内的最大子段和。 数据范围：$n,m\le 5\times 10^4$。 这题有一个经典做法，就是用线段树维护区间的最大前缀和、最大后缀和、总和、最大子段和再进行合并，但这并不是我们今天要讨论的。 考虑朴素的 dp 转移方程，设 $f_i$ 表示以 $i$ 结尾的最大子段和，$g_i$ 表示 $\max\limits_{j\le i} f_j$，有转移 $\left\{ \begin{array}{lr} f_i=\max(f_{i-1}+a_i,a_i) \\ g_i=\max(g_{i-1},f_i) \end{array} \right.$ 我们需要构造一个转移矩阵，使得 $\begin{bmatrix} f_{i-1} & g_{i-1} & \cdots\end{bmatrix}$ $\begin{bmatrix} a_i & \cdots \\ \vdots & \ddots \end{bmatrix}$ $=$ $\begin{bmatrix} f_i & g_i & \cdots\end{bmatrix}$。 此时你会发现，我们需要用到一个矩阵乘法里不涉及的运算：$\max$。 于是我们需要重定义矩阵乘法：$C_{i,j}=\max \limits_{k}A_{i,k}+B_{k,j}$。 这里也可以使用 $\min$，具体按照 dp 转移方程而定。 回到本题，我们可以将状态设为：$\begin{bmatrix} f_j & 0 & g_j \end{bmatrix}$，并构造出这样的转移矩阵：$\begin{bmatrix}a_i & -\infty & a_i \\ a_i & 0 & a_i \\ -\infty & -\infty & 0\end{bmatrix}$。 手动模拟一下转移过程，可以发现得到的新矩阵为：$\begin{bmatrix}\max\{f_j+a_i,0+a_i,g_j+-\infty\} & \max\{f_j+-\infty,0+0,g_j+-\infty\} & \max\{f_j+a_i,0+a_i,g_j+0\}\end{bmatrix}$，整理得： $\begin{bmatrix}\max\{f_j+a_i,a_i\} & 0 & \max\{f_j+a_i,a_i,g_j\}\end{bmatrix}$。 对照我们之前推出来的式子，我们惊喜的发现这个矩阵就是 $\begin{bmatrix}f_i & 0 & g_i\end{bmatrix}$。 不难发现，我们新定义的运算是满足结合律的（证明请自行百度），于是可以利用线段树快速求出一段区间的矩阵的乘积，从而进行转移。 再来分析一下时间复杂度，一次矩阵乘法的复杂度是 $O(a^3)$ 的，其中 $a$ 为矩阵的边长，线段树查询一段区间的信息是 $O(\log n)$ 的，故总时间复杂度为 $O((n+m)a^3\log n)$。 SP1716 GSS3 - Can you answer these queries III 题意简述：给出长度为 $n$ 的序列 $a$ 以及 $m$ 组操作，操作 `0 x y` 表示把 $a_x$ 修改为 $y$，操作 `1 l r` 表示询问区间 $[l,r]$ 的最大子段和。 数据范围：$n,m\le 5\times 10^4$。 可以发现其实就是 GSS1 多了个单点修改，那么只要在线段树上修改对应点的信息即可。 CF750E New Year and Old Subsequence 题意简述：给出长度为 $n$ 的序列 $a$ 以及 $m$ 组询问，对每组询问回答 $a$ 的子串 $[l_i,r_i]$ 至少删去多少个字符后才能使得其不包含子序列 2016 而包含 2017。 数据范围：$n,m\le 2\times 10^5$。 设 $f_{i,0/1/2/3/4}$ 分别表示当前子串末尾为 $i$ 时包含$ \varnothing/2/20/201/2017$ 最少需要删去多少个字符，那么有 $\left\{ \begin{array}{lr} f_{i,0}=f_{i-1,0}+[s_i=2] \\ f_{i,1}=\min(f_{i-1,1}+[s_i=0],f_{i-1,0}[s_i=2]) \\ f_{i,2}=\min(f_{i-1,2}+[s_i=1],f_{i-1,1}[s_i=0]) \\ f_{i,3}=\min(f_{i-1,3}+[s_i=7\ \lor\ s_i=6],f_{i-1,2}[s_i=1]) \\ f_{i,4}=\min(f_{i-1,4}+[s_i=6],f_{i-1,3}[s_i=7]) \end{array} \right.$ 构造出转移矩阵后进行动态 dp 即可。 一个 trick： 可以发现我们的答案矩阵其实只有一行，那么在线段树上查询的时候只用完成第一行的矩阵乘法。（注意是查询，在线段树 push_up 的时候还是得用正常的矩阵乘法）。 使用该 trick 后 966ms -> 607ms。优化还是较明显的。 CF573D Bear and Cavalry 题意简述：有 $n$ 个人和 $n$ 匹马，第 $i$ 个人对应第 $i$ 匹马，要求每个人都不能骑自己对应的马。第 $i$ 个人的能力值为 $w_i$，第 $i$ 匹马的能力值为 $h_i$，第 $i$ 个人骑第 $j$ 匹马的能力值为 $w_ih_j$，整个军队的总能力值为 $\sum w_ih_j$（一个人只能骑一匹马，一匹马只能被一个人骑）。有 $m$ 个操作，每次给出 $a,b$，交换 $a$ 和 $b$ 对应的马。每次操作后你都需要输出最大的总能力值。 数据范围：$n\le 3\times10^4$，$m\le 10^4$。 有这样的结论：我们把 $w,h$ 排序后，每个人 $i$ 匹配的马必定在 $[i-2, i+2]$ 中。 这里直接引用 @_sys 的证明： 于是设 $f_i$表示前 $i$ 个人和前 $i$ 匹马匹配完成的最大权值，则有转移 $f_i=\max\limits_{j\ge i-3}{f_j+calc(j+1,i)}$。 其中 $calc(l,r)$ 表示 $[l,r]$ 区间内满足每个人不骑自己对应的马的最大总能力值，可以 $O((r-l+1)!)$ 枚举每种情况计算。 最后构造出转移矩阵并进行动态 dp 即可。 P4719 【模板】"动态 DP"&动态树分治 题意简述：给定一棵 $n$ 个点的树，$i$ 号点的点权为 $a_i$。有 $m$ 次操作，每次操作给定 $x,y$，表示修改点 $x$ 的权值为 $y$。你需要在每次操作之后求出这棵树的最大权独立集的权值大小。 数据范围：$n,m\le 10^5$。 先考虑没有修改的情况下怎么做。首先先选取 1 号点作为全树的根。然后我们设 $f_{i,0}$ 表示不选择 $i$ 号点时，以 $i$ 号点为根的子树的最大权独立集；$f_{i,1}$ 表示选择 $i$ 号点时，以 $i$ 号点为根的子树的最大权独立集。则有如下转移方程： $\left\{ \begin{array}{lr} f_{i,0}=\sum\limits_{j\in son_i} \max(f_{j,0},f_{j,1}) \\ f_{i,1}=\sum\limits_{j\in son_i} f_{j,0} + a_i \end{array} \right.$ 答案就是 $\max(f_{1, 0}, f_{1, 1})$。 然后你熟练地准备构造转移矩阵，却发现无从下手：序列上的 dp 是 “一对一” 转移，而树上的 dp 是 “多对一” 转移，即要考虑到每个儿子。 那么如何把这个转化成 “一对一” 转移的形式呢？这就要用到树链剖分了。 设 $g_{i,0}$ 表示 $i$ 号点的所有轻儿子可取可不取，且不取 $i$ 的最大权独立集，$g_{i,1}$ 表示 $i$ 号点的所有轻儿子都不取，且取了 $i$ 的最大权独立集，$j$ 为 $i$ 的重儿子。则有如下转移方程： $\left\{ \begin{array}{lr} f_{i,0}=g_{i,0}+\max(f_{j,0},f_{j,1}) \\ f_{i,1}=g_{i,1}+ f_{j,0} \end{array} \right.$ 这样就在转移时就只需要考虑重儿子了。相应的转移矩阵也不难构造，请自行尝试。 那么问题来了：带修改操作，如何维护 $g$ 呢？ 对于一条重链，求出这条重链上矩阵的乘积，这就是这条重链链头对它父亲的贡献（显然重链链头是他父亲的轻儿子），将父亲的 $g$ 减去贡献后，更新重链上需要修改的点的矩阵，再将新的乘积对父亲的 $g$ 的贡献求出并加上。完成这一切后，父亲成为新的需要修改的点，父亲所在重链成为新的需要处理贡献的重链，就这样处理下去，直到重链链头为根为止。 由于树剖带一个 $\log$，因此总时间复杂度为 $O(na^3 \log^2 n)$。 [NOIP2018 提高组] 保卫王国 题意简述：给定一棵 $n$ 个点的树，给 $i$ 号点染色的花费为 $a_i$，要求任2个相邻点至少有1个被染色。给出 $m$ 组询问，每次强制两个点的状态(染/不染)，求出每次询问的最小花费。 数据范围：$n,m\le 10^5$。 设 $f_{i,0}$ 表示 $i$ 号点不染色的最小花费，$f_{i,1}$ 表示 $i$ 号点染色的最小花费，则有如下转移： $\left\{ \begin{array}{lr} f_{i,0}=\sum\limits_{j\in son_i} f_{j,1} \\ f_{i,1}=\sum\limits_{j\in son_i} \min(f_{j,0},f_{j,1})+a_i \end{array} \right.$ 于是按照与模板题相同的方法动态 dp 即可。 课后练习： - CF1609E William The Oblivious - 前两天的 CF，感觉大家都场切了（ - CF1286D LCC - P3781 [SDOI2017]切树游戏 - 这题的 hack 数据卡树剖 /fn，大家可以去学一下 “全局平衡二叉树” 的黑科技。