DP复习

Posted by Panda2134's Blog on April 16, 2018

HNOI2018 d2t3 那么水的树上DP都没看出来,让我意识到现在的DP水平可能还不如NOIP之前……去雅礼之前这个星期来复健一下……
仔细想想,我的省选算法除了网络流和树剖、平衡树之外真的没有学的特别好的…… NOIP的时候就是DP救了我……九省联考网络流却炸了……不管怎么说先搞搞DP吧


[HNOI2018] 道路

mmp当时在考场上把问题一般化为了多元函数的最值……写了个模拟退火,好像挂掉了……HN有神犇模拟退火A了…… 以及全部翻修公路70分什么鬼……(实际是75分,感谢yyb神犇教导 $\leftarrow$ 就是这个人模拟退火 A 了,膜拜)

Solution:
状态:f[u][x][y] 代表在节点 $u$ ,到根的路径上未翻修公路铁路数目为 $x, y$,子树内所有叶子的最小不便利值。

决策:如果 $u$ 是城市,考虑翻修公路还是铁路,直接从儿子转移,如果 $u$ 是乡村,直接就有 f[u][x][y] = ci * (ai + x) * (bi + y). 直接转移即可。

注意到答案需要long long,而它占用 8 Bytes ,所以直接开 DP 数组会 MLE! DFS 的时候在栈里面开数组,然后把儿子的状态数组回传即可。这样状态数组的空间复杂度就是常数了。

[NOIP2017] 宝藏

要是这个题目出现在了 HNOI2018 ,保证我现在做不出来……然而 NOIP 的时候只用了 1h20min 就A了……真的气

Solution:
首先枚举打通地面的是哪个宝藏屋,以下称为根。

状态:设 f[S][u]为当前开凿了 $S$ 集合内所有点,且生成树满足总代价最小的时候,$u$ 到根的距离;g[S] 为当前开凿了 $S$ 集合内点,已开发部分的最小总代价(注意不是剩下部分的最小总代价,否则不满足无后效性,无法转移)。

决策:考虑枚举最后加入生成树的边。

于是一定有转移:

\[g(S) = \min_{S' \subseteq S} \{g(S') + L \cdot f(S', u)\}\] \[f(S, u) = \begin{cases} f(S', u) &\text{当}g(S)\text{不在}u\text{取得最小值} \\ f(S', v) + 1 &\text{当}g(S)\text{在}u\text{取得最小值},(u, v)\text{为原图中边} \end{cases}\]

记忆化搜索即可。注意特判含有不包含根的连通块时,最小总代价为 $+\infty$.

[SDOI2009] 学校食堂

坑了6个月了……今天填上
回忆DP的要点:把转移需要的量放进状态

Solution: 状态:$f(i, j, S)$ 代表当前考虑第 $i$ 个人(Ta还没有吃饭),上一个吃到饭的是第 $j$ 个人,且 $i+1 \sim i+b_i$ 的人状态为 $S$,往后的最小代价。

决策:$i$ 吃到饭还是 $i+1 \sim i+b_i$ 中的一个吃到饭。如果是 第 $k$ 个吃到饭,则要综合考虑 $i \sim k-1$ 的限制。

转移:

\[f(i, j, S) = \min \begin{cases} f(i, k, S\cup\{k\}) + cost(j, k) \\ f(i', i, S') + cost(j, i) \end{cases}\]

边界为 $f(n+1, *, \varnothing) = 0$.

复杂度为 $O(nb^22^b)$($b$为最大忍受度),可以接受。

注意: 有一点非常坑!因为 $b_i \le 7$,所以可能一个人(称为甲)身后7个人都吃了饭Ta才吃,在Ta吃了之后吃的那个人不妨称为乙,则乙的坐标减去甲的坐标等于8!所以说转移的时候 $k$ 应该取 $[i-8, i+7] \cap \mathbb{Z}$ 内的所有值!

[NOIP2017] 逛公园

Solution:

DP+图论的好题,可惜考场上由于 $a \times b - a - b$ 的影响没能写出来=.=

先考虑70分部分分:

状态:$f(u, d)$ 表示当前在 $u$ 点,到 $n$ 点距离为 $d$ 的路径条数

决策:走哪个邻接点

转移:

\[f(u, d) = \sum_{<u, v> \in \mathbb{E}} f(v, d - \text{len}_{<u, v>})\]

考虑如何实现:因为 $0 \le k \le 50$,所以有用的状态最多有 $O(nk)$ 个。比较暴力的做法是用一个map / unordered_map 存状态,但前者带 $\log$,后者有一定常数,都只能拿到 60 分。

稍微仔细想想就可以知道,如果 $\text{dist}_t[u]$ 为建立反图后的 $<u, t>$ 距离,那么只有 $d \ge \text{dist}_t[u]$ 时才可能有解,否则答案一定是0.(不可能有比 $<u, t>$ 最短路更短的路径!)这样的话,用数组 opt[200000+10][50+10] 即可存储(存储的时候第二维下标用 $d - \text{dist}_t[u]$)

再看满分做法:由于 0 边的存在,可能状态转移出现环,就不再满足动态规划 DAG 的要求了。我们发现,只有 0 环对此类决策有影响。我们考虑所有0边的导出子图,求出其上的所有强连通分量。如果某个强连通分量大小 $\ge 2$ ,那么它就是一个 0 环。(不一定是简单环,但这不影响)

考虑把这样的 0 环缩成 1 个点,称缩的某个点为 $P$。如果缩点后 $1 \sim P \sim n$ 的路径长度 $\in [\text{dist}_{s, t}, \text{dist}_{s, t}+k]$ ,那么显然有无穷多路径,否则这个 0 环对答案没有影响,可以删去。经过如此处理后就转化为了 70 分部分分的情况。至此问题解决。

[JLOI2014]天天酷跑

多段图路径问题,类似于[NOIP2014]飞扬的小鸟

状态:设 $f(i, j, h, c)$ 代表在 $(i, j)$ 点,这次跳跃剩余上升高度 $h$ ,剩余连跳次数 $c$ ,从开始时到 $i-1$ 列的最大收益。

转移:设 $p, q$ 为最大连跳次数和最大跳跃高度。

  • 分类讨论:
  • $j > 1$:
    • $h > 0$
      • $j < m​$ 时:$f(i, j, h, c)\rightarrow f(i+1, j+1, h-1, c)​$ (继续上升)
    • $h = 0$
      • $j > 2$ 时:$f(i, j, h, c) \rightarrow f(i+1, j-1, 0, c)$ (下降)
      • $j < m \text{ 且 } c > 0$ 时:$f(i, j, h, c) \rightarrow f(i+1, j+1, q-1, c-1)$ (连跳)
      • $j = 2$ 时:$f(i, j, h, c) \rightarrow f(i+1, 1, 0, 0)$ (落地)
  • $j = 1$:
    • $j < m$ 时:$f(i, 1, 0, 0) \rightarrow f(i+1, 2, q-1, p-1)$ (起跳)
    • $f(i, 1, 0, 0) \rightarrow f(i+1, 1, 0, 0)$ (走路)

注意:

  1. 空间开不下,用滚动数组,$i+1$ 之前把当前位置清理干净(不要把清理语句写在if内!!!)
  2. 刷表的时候,每到一个新的 $i$ ,就用 $-\infty$ 覆盖掉所有不可达位置
  3. 跑到 $n+1$ 才算结束

[WC2008]游览计划

最开始看上去有点像是求出一个类似虚树的东西:包含所有的关键点,而且总价值最小。

后来才知道这玩意叫做斯坦纳树

然后就去学习了一发= =

状态:$f(i, j, S)$ 表示以 $(i, j)$ 为树根,连通了景点集合 $S$ 的最小代价。

决策:

  • 合并 $2$ 棵斯坦纳树
  • 从上下左右的树根转移

转移:

  • $f(i, j, S) = \min_{\varnothing \subsetneq S’ \subsetneq S}{f(i, j, S’) + f(i, j, S - S’) - \text{val}_{(i, j)}}$
  • $f(i, j, S) = \min{f(i’, j’, S’) + \text{val}_{(i, j)}}$

边界:当 $(i, j)$ 为景点时,$f(i, j, (i, j)) = 0$.

注意到状态并不满足无后效性,所以说不能直接DP;发现如果采用刷表法的话,后一个操作相当于最短路中的松弛,所以可以用 SPFA 实现。

[HNOI2007] 梦幻岛宝珠

采用泛化物品合并解决。题解

[SCOI2014] 方伯伯的玉米田

一开始看到区间加法,想到差分后 &^#^%#%^$#@%#@% ,然后发现不仅复杂度爆炸,而且无法优化……

看题解第一行,看到一个并不显然的结论:拔高区间终点一定是 $n$.

证明:如果拔高区间的右侧还有数字的话,那么原来在 LIS 中的某些右侧数字在区间加法后可能离开 LIS ,答案肯定不如拔高区间右侧没有数字的情况好。

然后进行DP.

Solution:

状态:$f(i, j)$ 表示当前考虑第 $i$ 个玉米,已经拔高了 $j$ 次(这个玉米在 $j$ 个区间中)

决策:考虑前驱点、当前点拔高了几次(被坑了很久的一点:当前点可以多次拔高!)

转移:

\[f(i, j) = \max_{a_{i'} + j' \le a_i + j, j' \le j}f(i', j') + 1\]

以 $j$ 为 $x$ 轴(需要平移 $1$ 个单位),$a_i + j$ 为 $y$ 轴,就转化为了二维数点。用二维数点的数据结构实现即可。

最开始写的二维线段树,T 飞;不服,写 zkw 线段树套 zkw 线段树,居然还 TLE ……

改成二维 BIT ,终于过了……