2020-03-07 23:03 一中 C++

关注

DP浅谈

$DP$ 浅谈

由于窝太菜了，只好写这篇浅谈来聊以***。

那么我们从最简单的 $DP$ 入门开始吧

【一】基础 $DP$

$(I)\ \ lis$ 一个最基础的 $DP$ 入门题。

状态： $f_i$ 表示到 $i$ 的 $lis$ 长度
转移： $f_i=\max\ (f_j+1)\ \ (a_j\leq a_i)$
答案统计： $\max \ f_i$
因为我们在更新 $i$ 时要找到最大的 $f_j$ 来更新答案使得答案最优。这样的复杂度是 $\ O(n^2)$
但是我们可以在 $\ O(n \log n)$ 的时间内完成，此时可以用树状数组来维护。这里来讲一下用树状数组来维护。此时只要利用简单的区间求最值以及区间加就能完成。
AT2827 LIS例题
随便再来几道线性 $DP$ ：

$(1)$ 例题一：CF711C

这算是一道比较简单的 $DP$ 题

$f_{i,j,k}$ 表示表示前i颗树已经分成k组，第i颗树的颜色是j的情况花费的最小费用。

转移也很简单（就是思考这个状态可以由哪些状态转移过来就行了）

当 $a_i$ 确定的时候：

$f_{i,a_i,k}=max(f_{i,a_i,k},f_{i-1,j,k-1})\ \ (j!=a[i])$

$f_{i,a_i,k}=max(f_{i,a_i,k},f_{i-1,j,k})\ \ (j==a[i])$

当 $a_i$ 不确定的时候：

$f_{i,j,k}=max(f_{i,j,k},f_{i-1,h,k-1}+w_{i,j})\ \ (j!=h)$

$f_{i,j,k}=max(f_{i,j,k},f_{i-1,h,k}+w_{i,j})\ \ (j==h)$

这种题目只要把所有转移考虑全面就很简单了。

参考代码

$(2)$ 例题二：CF706C

$(3)$ 例题三：CF404D

【二】 $DP$ 的优化

由于蒟蒻比较菜不知道什么神仙优化方法，就写几种基础的就好了。

$(I)$ 单调队列优化 $DP$

其实单调队列就是一种队列内的元素有单调性（单调递增或者单调递减）的队列，答案（也就是最优解）就存在队首，而队尾则是最后进队的元素。因为其单调性所以经常会被用来维护区间最值或者降低DP的维数已达到降维来减少空间及时间的目的。（引出处）
我们一边看例题一边来理解他的妙处所在。

例题一：P6040

对于暴力：

设 $f_{i}$ 表示到 $i$ 的最小花费精力，转移 $O(n^2)$ 即可

转移也很简单，没什么可以讲的：

$f_i=min\{f_j+(i-j-1)*d+k+a_i\},j∈[i-x,i-1)$
现在我们就要使用单调队列来优化

对于上述柿子我们可以进行移项合并得到： $f_i=a_i+k+(i-1)*d+min\{f_j-j*d\}$

到这里我们想到用单调队列去维护 $f_j-j*d$ 单减即可。

对于每次距离的限制用对头来控制，如果 $i-q[head]>X$ 那么要更新队头（可以认为队头是来控制区间范围的），对于 $DP$ 值的更新要用到队尾，即当 $f[q[tail]]-q[tail]*D>=f[i]-i*D$ 时要更新队尾来保证队内元素单调递减。这样我们就很好地维护了一个单调队列。
参考代码

$(2)$ 例题二：P2569

$(2^{'})$ 我写的题解（可参考）

$(3)$ 例题三：CF372C

$(II)$ 线段树优化 $DP$

注：由于窝比较菜，只会一些很套路的，巨佬请让步。
以下是我的个人观点：因为线段树可以维护一些区间加，区间 $\min or \max$ 。。而 $DP$ 不是有时也是寻找从哪里转移过来时候，为了最优，可以使用线段树。或者只是对 $DP$ 方程式中的一部分进行快速查询与记录。一般可以把 $n^2$ 变成 $n\log n$ 。话不多说，还是来看几道例题。

例题一：CF629D

对于暴力

暴力 $DP$ 很简单设 $f_i$ 表示到第 $i$ 块蛋糕最大体积

转移也很显然： $f_i=\max{f_j}+V_i(j\leq i,a_j<a_i)$
我们考虑用线段树优化，不是很明显就是用线段树去找到最大的 $f_j$ 来转移，那么不是只要维护一个区间最大以及区间修改就行了。每次更新完 $f_i$ ，把 $[1,id_i]$ 用 $f_i$ 来更新。我是用树状数组的，常数稍微小一点。
参考代码

例题二：CF115E

这道题目相对上面那题难一点。
对于暴力 $f_i$ 表示只考虑修前 $i$ 条路的最大收益，转移非常显然： $f_i=\max(f_j+P(j+1,i)-A(j+1,i))$ ，其中 $P(i,j)$ 表示这个区间的收益， $A(i,j)$ 表示这个区间的修理费。
我们还是来考虑线段树优化。首先要保证无后效性，我们按右端点排序，然后从 $1$ 到 $n$ 修路，每个点的左边区间减去修理费，遇到比赛的右端点，在左区间加上收益，反复更新即可。这些区间更新修改操作都可以用线段树实现。
参考代码

$(3)$ 例题三：CF833B

$(4)$ 例题四：CF1304F2（虽然本人就做了F1）

$(III)$ 长链剖分优化 $DP$

由于没有怎么学习这里先咕咕咕。。

【三】进阶 $DP$

再次申明：由于博主比较菜只会写众所周知的进阶 $DP$

$(I)$ 状压 $DP$

一下是我的个人看法：状压 $DP$ 就是对于 $(n\leq 20)$ 但爆搜又无法完成时使用的~~（是不是非常有道理）~~。认真些，其实状压 $DP$ 就是把某些状态用二进制来存（ $1$ 表示出现过, $0$ 则相反）。
但是在学习状压 $DP$ 之前先要比较熟悉位运算状压之位运算
我们还是拿几道题目来看看吧。

例题一：CF115E

对于暴力很简单，不再赘述。
我们首先要知道 $b_i∈[1,59]$ 为什么是 $59$ 呢。我们可以得到 $b_i$ 只会在 $60$ 以内，所以会出现的数字只有 $1$ 和 $60$ 以内的质数。而对于 $59$ 来说，完全可以用 $1$ 代替，所以现在会出现的数字被缩减为 $17$ 个了。应该讲得比较清楚。这样我们对于每个质数进行二进制表示来实现状压。

于是我们设 $f_{i,s}$ 表示与 $a_i$ 匹配到 $i$ 时的质数集状态为 $s$ 的 $\sum a_i-b_i$ 的最小值。再用 $g_{i,s}$ 来记录路径，这样就随意转移即可。

大概为 $f_{i+1,s|sta_k}=\max(f_{i+1,s|sta_k},f_{i,s}+abs(a_i-k))$ ，其中 $k$ 为 $[1,59]$ 的质数枚举， $sta_k$ 为对每个质数存下的状态。 $g_{i,s}$ 随 $f_{i,s}$ 的更新一起更新即可。输出方案时候我们只要不停回溯最终状态即可，即 $\oplus nowsta$ 。
参考程序

例题二：CF1316E

一道刚刚的 $codeforces$ 的比赛题，挺好的。
有数据范围 $(p\leq 7)$ 可得此题为状压 $DP$ 。

我们首先建个结构体，然后对观众的收益进行排序，再做 $DP$ 。

我们设 $f_{i,s}$ 表示到第 $i$ 个人时候， $p$ 个位置的状态为 $s$ 时候的最大收益。

转移比较容易

$(1)$ 若不能再选观众了： $f_{i,s}=\max(f_{i-1,s\ xor\ (1<<j-1)+a_{i,j},f_{i,s})}$

$(2)$ 还能选： $f_{i,s}=\max(f_{i,s},f_{i-1,s}+v_i)$
参考代码

$(3)$ 例题三：CF8C（要加个奇妙的剪枝）

$(4)$ 例题四：CF580D（比较简单）

$(II)$ 树形 $DP$

树形 $DP$ 顾名思义就是在一棵树上面做 $DP$ ，是不是很简单啊。他有着和普通 $DP$ 一样的分类（比如背包）。转移相对线性比较难理解，所以还是需要好好理解一下的。那么我们先来看几道题目吧。

$(i)$ 树上背包

树上背包就是把背包做到树上就好了，与线性 $DP$ 套路相似。

例题一：P2014 [CTSC1997]选课

这是一道非常经典的题目，首先我们设 $f_{i,j}$ 表示选择以 $i$ 为根的子树中 $j$ 个节点的最大收益。
然后就是分组背包的转移了： $f_{u,j}=\max(f_{u,j},f_{v,k}+f_{u,j-k})(v∈S_u,k\leq j)$
答案 $f_{1,m}$ (这边我把根变成 $1$ 而不是题目里的 $0$ )
参考代码

例题二：P2515 [HAOI2010]软件安装

这道题目是一道综合应用题，需要用到 $tarjan$ 缩点。
我们先按照某些依赖关系去连边，然后把相互依赖的一些软件进行缩点。缩完点后，再建一遍图。（以上是 $tarjan$ 部分）由于建立出来的是一棵树，我们建立一个虚拟点 $rt$ 以虚拟节点作为根。那么我们就可以在上面进行 $DP$ 啦，下面就与例题一同理了。
状态：设 $f_{i,j}$ 为以 $i$ 号点为根的子树中用不超过 $j$ 的空间的最大价值。
转移： $f[u][i+w[u]]=max(f[u][i+w[u]],f[u][i+w[u]-j]+f[v][j])$
答案就是: $f_{rt,m}$
参考代码

$(ii)$ 一般树形 $DP$

做了几道这样的题目发现其实从 $u$ 转移到 $v$ 其实就是 $siz,dep$ 之间的转移变化，如果无法理解这句话，我们开看一道题目。

例题一：P2986 Great Cow Gathering G

这是一道必做题，初学的都要做
我们设 $f_v$ 表示以 $v$ 为牛棚的花费，只要有 $fa_v$ 转移过来即可。对于转移画几个图随便想想就可以得到。
转移: $f_v=f_u-siz_v\times w+(tot-siz_v) \times w$
应该比较好理解，就是父亲向儿子走了一步，那么父亲与儿子的连边产生的贡献即 $siz_v\times w+(tot-siz_v) \times w$ 。还是很显然的。
参考代码

$...$ 准备填坑