RainAir
My OI Blog
RainAir
DDP 学习笔记

DDP(动态 dp),是通过将状态改写成矩阵,然后定义具有结合律的与转移等价的运算,用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。
NOIP2018 Day2T3 – 保卫王国
考场上根本不会…那个时候我是连暴力 dp 都不会的菜鸡,现在回来学一学。
我们来找一道简单的题目入手:给定一棵树,点有点权,每次可以修改一个点的权值,每次修改后求这棵树的最大独立集。$n \leq 10^5$
如果这个问题是静态的,我们可以设出状态 $f_{i,0/1}$ ,表示以 $i$ 为根的子树内, $i$ 这个点是否选择时的最大权值和。转移显然:
$$f_{i,0} = \sum_{v \in son_i} max\{f_{v,0},f_{v,1}\}$$
$$f_{i,1} = \sum_{v \in son_i} f_{v,0}$$
我们观察在 dfs 中该 dp 的转移方式:我们发现这类 dp 对儿子的转移顺序 没有要求,所以我们可以先从轻儿子转移,再从重儿子转移。我们将这棵树重链剖分后,对于重链上的每一个点,我们记录从它所有轻儿子转移来的最好状态 $lf_{v,0/1}$,转移和上面的差不多,只需要限制不从重儿子转移就可以了。
于是假设我们先处理处理出 $lf$,然后观察 $lf$ 和 $f$ 之间的关系:发现如果想求重链上每一个点的 f 值,我们只需要将这个链抽出来跑序列 dp 就可以了,我们记重儿子为 $hson$,转移如下:
$$f_{i,0} = lf_{i,0}+max\{f_{hson,0},f_{hson,1}\}$$
$$f_{i,1} = lf_{i,1}+f_{hson,0}$$
于是我们对于链上的一段查询就变成了彻彻底底的区间查询了。我们考虑在修改一个点的时候,如果能快速维护对序列 dp 的修改操作,我们在这个点所在重链所在的线段树上进行修改操作,然后调到链的 $fa$ 上继续修改,就可以在 $O(log^2n)$ 的时间复杂度内完成这一操作。
现在问题就在于如何快速维护这一操作了。我们在维护一般的有加油乘的 dp 时,我们都是用矩阵乘法,这次我们考虑定义矩阵的广义乘法运算:
$$C_{i,j} = \max_{k=1}^n\{A_{i,k},B_{k,j}\}$$
我们发现这个运算具有结合律,所以可以在线段树上维护。
所以我们考虑这个简单的问题的转移写到矩阵上应该是:
https://blog.aor.sd.cn/wp-content/uploads/2019/07/EC12628F-AF2C-4D74-80A5-BEFB0278BF61.jpg
于是树剖后用线段树维护广义矩阵乘,就可以在 $O(nlog^2n)$ 的时间复杂度内做出本题。如果要追求 $O(nlogn)$ 的时间复杂度,可以使用 LCT 或者是全局平衡树来维护(虽然我都不会 zbl)。
贴一下代码:

关于保卫王国

首先答案显然是全集-最大独立集,所以变成了最大独立集,每次钦定一些点是否选的问题。
我们可以让强制选的点设为一个极大值,最后在答案里减去就可以了。对于强制不选的点我们可以设为一个极小值,这样选了这个点一定不优就不会选。由于树剖常数比较大,所以我写了个 fread(
附代码(基本上差不多):

赞赏
知识共享许可协议
本文链接: https://blog.aor.sd.cn/archives/688
如文中无特殊声明,本文采用 CC BY-NC-SA 4.0 进行许可,转载请说明出处!
希望 NOIP 不要翻车,希望省选不要翻车
https://secure.gravatar.com/avatar/97c17c68a1e55e11bb5558bc0f10cc0d?s=256&d=mm&r=g

RainAir

文章作者

一个OIer。

发表评论

textsms
account_circle
email

RainAir

DDP 学习笔记
DDP(动态 dp),是通过将状态改写成矩阵,然后定义具有结合律的与转移等价的运算,用数据结构快速维护的一种方法。在 NOIP2018 时作为 Day2 T3 出现。 NOIP2018 Day2T3 - 保卫王国 考场…
扫描二维码继续阅读
2019-07-11
标签
近期评论