Geiz-Revive > 动态dp学习笔记

动态dp学习笔记

2019-08-03

动态dp

动态$dp$是指有修改的$dp$问题，通常的解决方法是把转移方程写成矩阵，然后用数据结构维护矩阵连乘积，这里的乘法是重定义的运算，取决于原dp问题的转移方程。比如最大子段和就是求和再取$max$。

但是维护连乘积的前提条件是在序列上，如果是在树上，就需要通过一些技巧转化为序列问题。

$\Large 例题\alpha$：

先来一道比较水的：

$Link$

$n$ 个数，$q$ 次操作$(n,q\le50000)$

操作0 x y$A_x$ 修改为$y$

操作1 l r询问区间$[l,r]$ 的最大子段和

$\large Solution 1:$

显然可以用线段树维护前后缀的最大和来解决，这里不再占用篇幅。

$\large Solution 2:$

考虑原转移方程的形式：$dp_i=max(dp_{i-1}+a[i],a[i]),ans=max(ans,dp_{i-1}+a[i],a[i])$

所以矩阵就可以写出来了：

$\left( \begin{matrix} tmp_{i-1}&ans_{i-1}&0\end{matrix} \right)\left( \begin{matrix}a_i&a_i&-inf\ -inf&0&-inf\ a_i&a_i&0\end{matrix} \right) = \left( \begin{matrix} tmp_{i}&ans_{i}&0\end{matrix} \right)$

我们将平常的矩阵乘法换成这样的形式$c[i][j]=max_k(a[i][k]+b[k][j])$

线段树维护那个大矩阵连乘积即可，修改就是把每个位置上的$a_i$改了再$pushup$

$\Large 例题\beta$：

$Link$

给定一棵$n$个点的树，点带点权。

有$m$次操作，每次操作给定$x,y$表示修改点$x$的权值为$y$。

你需要在每次操作之后求出这棵树的最大权独立集的权值大小。

没有修改肯定都会做，方程是：

$dp_{u,0}=\sum\limits_{v∈uson}max(dp_{v,0},dp_{v,1}),dp_{u,1}=val_u+\sum\limits_{v∈uson}dp_{v,0}$

其中$v$是$u$的儿子

重点在于如何把这个方程转化到能在序列上使用。

我们发现这个东西似乎可以变换一下顺序也没什么影响，所以我们可以一条重链一条重链的dp，每次到达一个重链的顶部的时候我们直接将这个重链全部塞到队列里，然后我们递归下去遍历和重链相连的所有重链，最后处理这个重链。

然后对于重链上的每个点，先根据轻儿子的$dp$值(因为轻儿子一定是其他重链的顶部所以dp值必定已经计算好)，计算出一个$ldp_{i,0/1}$，然后根据这个$ldp$值在重链上跑序列$dp$。

方程为：$ldp_{u,0}=\sum\limits_{v∈lightson}max(dp_{v,0},dp_{v,1}),ldp_{u,1}=\sum\limits_{v∈lightson}dp_{v,0}$

之后可以得到：$dp_{u,0}=max(dp_{heavy,0},dp_{heavy,1})+ldp_{u,0},dp_{u,1}=val_u+ldp_{u,1}+dp_{heavy,0}$

矩乘形式同上，矩阵为：

$\left( \begin{matrix}dp_{i-1,0}&dp_{i-1,1}\end{matrix} \right)\left( \begin{matrix}ldp_{i,0}&ldp_{i,1}\ldp_{i,0}&-∞\end{matrix} \right) = \left( \begin{matrix}dp_{i,0}&dp_{i,1} \end{matrix} \right)$

树剖就可以$nlog^2n$维护了

但是还有一个$log$的黑科技：“全局平衡二叉树”，也就是所谓的静态$lct$

以下引用自shadowice1984大佬的题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

众所周知把刚才的树剖换成lct就可以做到一个log了，但是我们发现lct实在是常数太!大!了！绝对是跑不过实现的优秀的一点的树剖的

但是我们对于lct的复杂度证明却很感兴趣，为啥同样是操作了logn个数据结构，把线段树换成常数更大的splay复杂度反而少了一个log呢？(刚才这句话严格来讲是病句，常数和复杂度没有任何关联)

具体证明需要用到势能分析，但是感性理解一下就是如果我们把lct上的虚边也看成splay的边的话，我们发现整棵lct变成了一棵大splay，只是有些点度数不是2了

但是这些点度不是2的点并未破坏splay的势能分析换句话说势能分析对整颗大splay仍然生效, 所以你的log次splay在整个大splay上只是一次splay而已

复杂度自然是均摊O(logn)了

但是，我们发现这是颗静态树，使用splay实在是大(常)材(数)小(过)用(大)了

于是我们考虑将lct强行静态化，换句话说，建一个像splay一样的全局平衡的树

观察到线段树只是局部平衡的，在碰到专业卡链剖的数据--链式堆(根号n个长度为根号n的链连成完全二叉树的形状)的时候会导致算上虚边之后的整颗树左倾或者右倾

此时我们发现如果在建线段树的时候做点手脚，我们把线段树换成二叉查找树bst，并且这个bst不是严格平衡的话，我们可以做到更加优秀的复杂度，使得算上虚边之后的树树高达到O(logn)级别

我们还是在树上dfs，但是对于重链建bst的时候我们并不建一个完美的bst，而是将每一个节点附上一个权值，权值为它所有轻儿子的siz之和 + 1，然后我们每次找这个链的带权重心，把他作为这一级的父亲，然后递归两边进行建bst。

当然我们发现最坏情况下我们可以建出一个严重左倾或者右倾的bst。

但是，我们考虑算上虚边的整颗树我们会发现一个神奇的性质，无论是经过一条重的二叉树边还是虚边，所在子树的siz至少翻一倍，而这个性质在原来的线段树上是没有的

所以这个大bst的高度是O(logn)的

写起来还是挺好写的。

$\Large 建树部分:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
struct matrix {
	int a[2][2];
	matrix() { a[0][0] = a[1][0] = a[0][1] = a[1][1] = -inf; }
	matrix(bool x) { a[0][0] = a[1][1] = 0, a[0][1] = a[1][0] = -inf; }
	friend matrix operator*(matrix a, matrix b) {
		matrix c;
		for (re i = 0; i < 2; i++) {
			for (re j = 0; j < 2; j++) {
				for (re k = 0; k < 2; k++) {
					c[i][j] = max(c[i][j], a[i][k] + b[k][j]);
				}
			}
		}
		return c;
	}
	inl int *operator[](int x) { return a[x]; }
	inl int getmax() { return max({ a[0][0], a[1][0], a[0][1], a[1][1] }); }
};
int siz[100001], h[100001];
vector<int> ve[100001];
inl void dfs(int x) {
	siz[x] = 1;
	for (auto y : ve[x]) {
		if (!siz[y]) {
			dfs(y), siz[x] += siz[y], siz[y] > siz[h[x]] ? h[x] = y : 0;
		}
	}
}
int ew[100001], v[100001], st[100001], top, rt;
bool vis[100001];
struct node {
	int child[2], fa;
	matrix mul, w;
} t[100001];
inl void pushup(int x) {
	t[x].mul = t[ls(x)].mul * t[x].w * t[rs(x)].mul;
}
inl void upd(int x, int y) {
	t[x].w[0][0] = (t[x].w[0][1] += t[y].mul.getmax());
	t[x].w[1][0] += max(t[y].mul[0][0], t[y].mul[0][1]);
	fa(y) = x;
}
inl int build(int l, int r) {
	if (l > r) return 0;
	re sum = 0;
	for (re i = l; i <= r; i++)
		sum += ew[st[i]];
	for (re i = l, now = ew[st[i]]; i <= r; now += ew[st[++i]]) {
		if ((now << 1) >= sum) {
			ls(st[i]) = build(l, i - 1), rs(st[i]) = build(i + 1, r), pushup(st[i]);
			if (ls(st[i])) fa(ls(st[i])) = st[i];
			if (rs(st[i])) fa(rs(st[i])) = st[i];
			return st[i];
		}
	}
	return 0;
}
inl int build(int x) {
	for (re i = x; i; i = h[i])
		ew[i] = siz[i] - siz[h[i]], vis[i] = 1;
	for (re i = x; i; i = h[i]) {
		for (auto y : ve[i]) {
			if (!vis[y]) upd(i, build(y));
		}
	}
	top = 0; for (re i = x; i; i = h[i])st[++top] = i;
	return build(1, top);
}

$\Large 修改：$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inl bool isroot(int x) {
	return ls(fa(x)) != x && rs(fa(x)) != x;
}
inl void modify(int x, int w) {
	t[x].w[1][0] += w - v[x], v[x] = w;
	for (re i = x; i; i = fa(i)) {
		if (isroot(i) && fa(i)) {
			t[fa(i)].w[0][1] = (t[fa(i)].w[0][0] -= t[i].mul.getmax());
			t[fa(i)].w[1][0] -= max(t[i].mul[0][1], t[i].mul[0][0]);
			pushup(i);
			t[fa(i)].w[0][1] = (t[fa(i)].w[0][0] += t[i].mul.getmax());
			t[fa(i)].w[1][0] += max(t[i].mul[0][1], t[i].mul[0][0]);
		}
		pushup(i);
	}
}

复杂度达到了优秀的一个$log$，并且常数也挺小的，跑的确实比树剖快，用这个就可以过掉强化版了。

强化版link

$\Large 例题\gamma$：

这题算是老熟人了……，$noip2018D2T3$ 保卫王国

动态$dp$板子题啊，把刚才的模板题稍微改一下就可以了（然而我还是重新写了一遍），本题所求即为总权值-带权最大独立集权值，修改就是改成正负$inf$，随便改一下就过了，当然也可以重新推个式子，式子也是非常的好推，这里就不在展示了。

先写这么多，由于现在找不到题单，之后可能会更新。。。