跳转至

经典动态规划模型

大概这篇博文就只能熟悉一下各大dp模型吧?

区间dp

概述

区间dp是dp的一种,一般处理在一个序列上的关于区间的一些问题。

因为 \([l, r]\) 这个区间,可以用很多个 \([l, k] \bigcap (k, r]\) 重复地 覆盖,

也就是通过枚举断点 \(k\),来实现区间 \([l, r] \gets [l, k] + (k, r]\) 信息的转移。

\(f(l, r) = \operatorname{op}\\{f(l, k) + f(k + 1, r)\\} \quad k \in [l, r)\)

需要注意的是 \(k\) 的范围也不一定是 \([l, r)\),也有许多题是 \(k \in (l, r)\) 的,

这个时候我们就需要处理出 \(len = 2\) 的,然后 for 循环从 \(len = 3\) 开始。

例题

  1. 「NOI1995」石子合并

    解题思路

    拆环成链,令 \(a[n + 1\ldots 2n] \gets a[1 \ldots n]\),这样就把一个环形的问题转化到了序列上。

    \(f(l, r)\) 表示第 \(l\) 堆石子一直合并到第 \(r\) 堆石子,能获得的最大值;

    \(g(l, r)\) 表示第 \(l\) 堆石子一直合并到第 \(r\) 堆石子,能获得的最小值。

    因为 \([l, r]\) 可以被分成 \([l, k]\)\((k, r]\),所以我们可以这么转移: $$ \begin{aligned} f(l, r) & = \max\{sum_r - sum_{l - 1} + f(l, k) + f(k + 1, r)\} \quad k \in [l, r) \\ g(l, r) & = \max\{sum_r - sum_{l - 1} + g(l, k) + g(k + 1, r)\} \quad k \in [l, r) \end{aligned} $$

  2. 「一本通 5.1 例 3」凸多边形的划分

    解题思路

    我们将这个凸多边形的每个顶点顺时针排成一行,环上的顶点其实和序列没有区别。

    \(f(l, r)\) 表示第 \(l\) 个顶点到第 \(r\) 个顶点所组成的凸多边形划分后,能得到的最小值。

    因为 \(S(l, r)\) 可以被分成 \((l, k)\)\((k, r)\),再加上 \(a_l, a_r, a_k\) 的贡献,所以我们可以这么转移: $$ f(l, r) = \min\{f(l, k) + f(k, r) + a_l\cdot a_k\cdot a_r\} \quad k \in (l, r) $$

  3. 「NOIP2007」矩阵取数游戏

    解题思路

    注意到每一行的贡献其实是互不干扰的,所以我们分别对每一行进行 dp。

    \(f(l, r)\) 表示这一行取了 \(m - (r - l + 1)\) 步后,还剩 \([l, r]\) 能得到的最大值。

    因为 \(S(l, r)\) 可以是 \(S(l - 1, r) - a_{l - 1}\) 得来的,也可以是 \(S(l, r + 1) - a_{r + 1}\) 得来的,所以我们可以这么转移: $$ f(l, r) = \max \begin{cases} f(l - 1, r) + a_{l - 1} \cdot 2^{m - (r - l + 1)} \\ f(l, r + 1) + a_{r + 1} \cdot 2^{m - (r - l + 1)} \end{cases} $$

  4. 「CF Edu #83」E. Array Shrinking

    解题思路

    这题比较综合,要先用区间dp预处理,然后再线性递推。

    \(f(l, r)\) 表示 \([l, r]\) 能缩合得到的数字(如果无法缩合,则 \(f(l, r) = 0\)

    \(g(i)\) 表示 \([1, i]\) 可以被分成的段数的最小值。

    如果 \([l, r]\) 能从 \([l, k]\)\((k, r]\) 组成,那么 \(f(l, k)\) 是应该等于 \(f(k + 1, r)\) 的,这样才能「缩合」。所以这么转移 \(f\): $$ f(l, r) = \max\{f(l, k) + 1\} \quad (k \in [l, r) \land f(l, k) = f(k + 1, r) > 0) $$

    因为 \([1, i]\) 能被分成 \([1, j]\)\((j, i]\) 两段,我们只用考虑 \((j, i]\) 能否缩合得到。所以我们可以这么转移: $$ g(i) = \min\{g(j) + 1\} \quad (j \in [1, i) \land f(j + 1, i) \neq 0) $$

树型dp

概述

树型dp是dp的一种,一般处理子树中最优解的一些问题。当然,也有「换根dp」之类的处理 整棵树 上最优解的一些问题。

例题

  1. 「一本通 5.2 例 4」战略游戏

    解题思路

    树型dp入门题。

    \(f(u, 0)\) 表示 \(u\) 上不放士兵,使得所有以 \(u\) 为根的子树中的 被「瞭望」到,所需放置的士兵最少个数。

    \(f(u, 1)\) 表示 \(u\) 上放士兵,使得所有以 \(u\) 为根的子树中的 被「瞭望」到,所需放置的士兵最少个数。

    \(u\) 上不放置士兵,那么所有的 \(v \in \textrm{son}(u)\) 上都得放士兵,才能使所有的边 \((u, v) \quad (v \in \textrm{son}(u))\) 被瞭望到;

    \(u\) 上放置了士兵,那么所有的 \(v \in \textrm{son}(u)\) 上需不需要放置士兵是随意的。所以我们可以这么转移: $$ \begin{aligned} f(u, 0) & = \sum_{v \in \textrm{son}(u)} f(v, 1) \\ f(u, 1) & = \sum_{v \in \textrm{son}(u)} \min\{f(v, 0), f(v, 1)\} \end{aligned} $$

  2. 「一本通 5.2 练习 2」旅游规划

    解题思路

    一个比较基础的换根dp。

    首先我们钦定一个根,对这棵有根树进行dfs;再换根,算出换根后的贡献。

    \(f(u, 0)\) 表示以 \(u\) 为根的子树中,最远的点的距离。

    \(f(u, 1)\) 表示以 \(u\) 为根的子树中,次远的点的距离。

    \(g(u)\) 表示以 \(u\) 为根的子树中,最远的点是在 哪一个孩子的子树中

    \(h(u)\) 表示不经过 \(u\) 的子树,最远的点的距离。

    不难发现,原来的无根树的直径,为 \(\max\\{f(i, 0), \max\\{f(i, 1), h(i)\\}\\}\),即

    从自己的某个孩子的子树中有一条路径一直延伸到另一个孩子,或者是这棵树的「另一半部分」。

    最后我们输出的,就是所有 \(f(i, 0), \max\\{f(i, 1), h(i)\\}\) 等于直径长度的 \(i\)

    在第一次dfs中,我们是 从孩子往双亲 转移的,方程是显然的: $$ \begin{aligned} f(u, 0) & = \max_{v \in \textrm{son}(u)}\{f(v, 0) + 1\} \\ f(u, 1) & = \textrm{second}\max_{v \in \textrm{son}(u)}\{f(v, 0) + 1\} \end{aligned} $$

    转移时顺便更新 \(g\) 即可。接下来我们要重点考虑的是 第二次dfs 会带来什么样的影响,也就是应该如何计算 \(h\) 值。

    第二次dfs是自顶向下的,也就是 从双亲往孩子 转移的。

    \(u\) 不经过子树的最长距离,肯定是 \(u\) 的父亲 \(x\) 能走一条特别远的路径出来。

    那么这条路径有两种可能:要么是 \(x\)\(x\) 的孩子(但不是 \(u\))的方向走,要么是 \(x\)\(x\) 的父亲 \(y\) 的方向走。

    如果 \(u\)\(g\) 中记录的最大孩子,那么第一种可能,就只能走次大孩子,即 \(f(x, 1)\);第二种可能就是 \(h(x)\)

    如果 \(u\) 不是 \(g\) 中记录的最大孩子,那么第一种可能,就能走最大孩子,即 \(f(x, 0)\);第二种可能还是 \(h(x)\)

    那么我们可以推导出转移方程: $$ h(v) = \begin{cases}\max\{h(u), f(u, 1)\} & v = g(u), u = \textrm{father}(v) \\ \max\{h(u), f(u, 0)\} & v \neq g(u), u = \textrm{father}(v)\end{cases} $$

状压dp

概述

假设有一行格子,要你黑白染色,你会怎么考虑表示这一行的状态呢?

假设 \(1\) 表示黑色,\(0\) 表示白色,那这一行是不是就等价于一个二进制数呢?

状压dp 就是通过用二进制数来表示状态的一种dp类型。

通常除了二进制,还有三进制(不能使用位运算,但是能暴力拆位)。

例题

  1. 「SCOI2005」互不侵犯

    解题思路

    状压dp 入门题。

    我们可以用一个 \(n\) 位二进制数 \(st\) 来表示这一行的状态,第 \(i\) 位为 \(1\) 表示这个格子上有王,为 \(0\) 则表示这个格子是空的。

    显然如果一个状态 \(st\) 是合法的,当且仅当 \(st \& (st / 2) = 0 \land st \& (st \cdot 2) = 0\)

    然后还要枚举上一行的状态,判断上一行的状态会不会和这一行的状态冲突。

    状态转移方程便是: $$ f(i, st, cnt) = \sum_{pr}f(i - 1, pr, cnt - \operatorname{popcount}(st)) $$

    其中 \(st, pr\) 均为合法状态,且 \(st\)\(pr\) 不冲突,后文同。

    \(\operatorname{popcount}(x)\) 表示 \(x\) 的二进制表示中 \(1\) 的个数。

    答案即为 \(\sum_{st}f(n, st, k)\)

  2. 「一本通 5.4 练习 1」涂抹果酱

    解题思路

    稍微有点复杂的三进制状态压缩。

    首先,一个状态是否是合法的,我们可以暴力求出这个状态的三进制表示。

    然后逐个判断相邻的两个位是否不同即可。

    其次,相邻两行的状态是否不会冲突,我们可以暴力同时取出这两个状态在三进制表示下的每一位,逐个比较是否相同即可。

    然后是转移,因为已经固定了第 \(k\) 行,我们可以看做是把这个棋盘分割成了 互不干扰\([1, k)\)\((k, n]\) 两部分。

    分别求出来方案数然后 相乘 即可得到最终答案。

    剩下的部分与 「SCOI2005」互不侵犯 类似,就不再赘述。

    状态转移方程如下: $$ f(i, st) = \sum_{pr}f(i - 1, pr) $$

    答案即为 $$ ans_{k}\cdot ans_{n - k + 1} = \left(\sum_{st}f(k, st)\right)\cdot\left(\sum_{st}f(n - k + 1, st)\right) $$

  3. 「APIO2007」动物园

    解题思路

    比较有技巧性的一道状压dp题。

    我们可以发现,一个人只能看见长度为 \(5\) 的「窗口」,所以我们可以利用这一点来进行状态压缩。我们把一个人能看到的动物压缩成一个二进制数,第 \(i\) 位为 \(1\) 表示能看见 \(i\) 这个动物,否则就看不见这个动物。

    首先我们预处理出 \(g(i, st)\),表示从第 \(i\) 个动物开始,往后的 \(5\) 个动物被移走,即移走状态为 \(st\) 时的满意人数。

    其次我们设 \(f(i, st)\) 表示 \([1, i]\),往后的 \(5\) 个动物被移走,即移走状态为 \(st\) 时的最大满意人数。

    可以推出状态转移方程: $$ f(i, st) = \max\{f(i - 1, st \cdot 2), f(i - 1, st \cdot 2 + 1) + g(i, st)\} $$

    我们从第 \(1\) 个开始枚举,然后要满足第 \(n + 1\) 个的状态和第 \(1\) 个状态相同即可。

数位dp

不会,咕着在。