【学习笔记】经典动态规划模型学习笔记

「用集合的角度来理解dp。」 $\gets$ 这个东西好像不是很好用。

大概这篇博文就只能熟悉一下各大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) \bigwedge 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) \bigwedge 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 \text{son}(u)$ 上都得放士兵,才能使所有的边 $(u, v) \quad (v \in \text{son}(u))$ 被瞭望到;

    若 $u$ 上放置了士兵,那么所有的 $v \in \text{son}(u)$ 上需不需要放置士兵是随意的。所以我们可以这么转移:

    $$
    \begin{aligned}
    f(u, 0) & = \sum_{v \in \text{son}(u)} f(v, 1) \\
    f(u, 1) & = \sum_{v \in \text{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 \text{son}(u)}\{f(v, 0) + 1\} \\
    f(u, 1) & = \text{second}\max_{v \in \text{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 = \text{father}(v) \\ \max\{h(u), f(u, 0)\} & v \neq g(u), u = \text{father}(v)\end{cases}
    $$

状压dp

概述

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

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

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

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

例题

  1. 「SCOI2005」互不侵犯

    状压dp 入门题。

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

    显然如果一个状态 $st$ 是合法的,当且仅当 $st&(st/2) = 0 \bigwedge st&(st\cdot2) = 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

作者

Clever_Jimmy

发布于

2020-04-27

更新于

2020-05-04

许可协议

评论

Your browser is out-of-date!

Update your browser to view this website correctly.&npsb;Update my browser now

×