动态DP 学习笔记

博主： tony102
发布时间：2021 年 06 月 10 日
1304 次浏览
暂无评论
2544字数
分类：总结

## 常见形式

动态DP 常用于解决树形DP 带点相关的东西的修改, 并询问每次修改(可永久可不永久)后的 DP 结果.

它的思想在于利用矩阵的结合律(以及运算的一些性质), 使其满足树链剖分一般使用的数据结构线段树的结合律, 再从轻重儿子对答案的贡献使得每次修改后需要重新 DP 的东西降到 $\Theta (n log^2 n)$ 类似的时间复杂度.

## 矩阵的结合律以及运算的结合律

最重要的一点就是利用两者的可结合来维护 DP

首先什么样的东西满足结合律?  例如加法和乘法: $(A + B) + C = A + (B + C)$ , $(AB) \times C = A \times (BC)$

把加法和乘法混在一起,是否还满足结合律? 也就是分配律: $A \times (B + C) = AB + AC = AC + AB$

为什么要在最后加上 $AC + AB$ ? 因为一个可以分配的东西内部必须可以满足交换律,这样结合相乘的东西交换才也能满足分配律.

我们原本在矩阵上的乘法是 $(+, \times)$ 形式的,也就是内部相乘外部相加.现在定义广义矩阵乘法内部运算可以改变,但应是新定义后的矩阵乘法 $(A, B)$ ( A,B 是两种二元运算)满足结合律.

满足结合律,有两个条件,上面已经介绍清楚了,现在提炼一下:

1. 运算 $A$ 对内部运算 $B$ 有分配律
2. 运算 $A, B$ 都有交换律

我们一般 DP 的 $min, max, +, \times$ 都是有结合律的.

## 具体方法

知道矩阵的运算可以结合后怎么套到树链剖分上来呢? 以 [Luogu4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) 为例,详细介绍

我们先设出不带修改求最大权独立集的树形 DP 方程, 设 $f_{u,0/1}$ 表示选或不选 $u$ 节点的最大权, 转移:

$$
\left\{
\begin{aligned}
f_{u,0}& = \sum_{v \in son(u)} max(f_{v,0}, f_{v,1}) \\
f_{u,1} & = w_u + \sum_{v \in son(u)} f_{v,0}
\end{aligned}
\right.
$$

一般步骤是移植到轻重链剖分时,单独考虑重儿子对 DP 的贡献.也就是设 $g_{u,0/1}$ 表示不选择 $u$ 且只选择 $u$ 的轻儿子和选择 $u$ 号点的答案.稍稍改改转移:

$$
\left\{
\begin{aligned}
f_{u,0}& = g_{u,0} + max(f_{heavyson(u), 0}, f_{heavyson(u), 1}) \\
f_{u,1} & = g_{u,1} + f_{heavyson(u), 0}
\end{aligned}
\right.
$$

怎么把这东西弄成一个易于在数据结构上维护且满足结合律的东西. 重定义矩阵乘法,使其变成一个 $(max, +)$ 的矩阵乘法,也就是内部加法外部取 `max` 的矩阵乘法.

来谈谈怎么快速构造出来,首先我们要的答案可以先写成一个方便的列向量

$$
\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix}
$$

要使两个矩阵经过我们定义的一个广义矩阵乘法变成一个 $2 * 1$ 的列向量,应该是由一个 $2 * 2$ 的矩阵和一个 $2 * 1$ 的矩阵相乘得到. 大小确定了,就要看转移方程. 以 $f_{i,0}$ 为例

$$
\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix} = \begin{bmatrix} g_{i,0} & g_{i,0} \\ g_{i,1} & -\infty\end{bmatrix} \times \begin{bmatrix} f_{heavyson,0} \\ f_{heavyson,1} \end{bmatrix}
$$

在这个新定义的矩阵乘法中 $f_{i,0} = max(g_{i,0} + f_{heavyson, 0}, g_{i,0} + f_{heavyson,1})$  因为满足结合律, 很明显 $g_{i,0}$ 在里在外都不影响运算的结果.

但$f_{i,1}$ 的转移中不需要 $f_{heavyson,1}$ 这一项的参与, 一般不需要参与的东西我们就用与运算方向相反的一个常量使这个值永远不会被取到. 例如现在的运算是 $max$ ,那么有 $-\infty$ 参与的项最终一定不构成答案.

现在已经知道了如何在线段树上结合维护,还需要考虑每次怎么改.

每一个修改,影响的只有上式中那个 $2*2$ 的矩阵. 因为在一条重链中,  $u$ 是重儿子,那么链顶的节点就会有它的矩阵转移过来.所以每次修改这个矩阵,然后修改链, 每次都把对应位置的变化量给加上去,注意同样要按照转移方程来写.

放了代码就算结束了吧

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e5 + 5, MAT = 5;
const int inf = 1e9;

int n, m, tim, num;
int w[SIZE], fa[SIZE], dep[SIZE];
int head[SIZE], dfn[SIZE], idx[SIZE], bel[SIZE], edp[SIZE], siz[SIZE], son[SIZE], f[SIZE][2], g[SIZE][2];

struct node {
	int to, nxt;
} edge[SIZE << 1];

struct matrix {
	int a[MAT][MAT];
	
	void clear() { memset(a, 0, sizeof(a)); }

matrix operator* (const matrix &b) const {
		matrix c; c.clear();
		for (int i = 0; i < 2; ++ i) {
			for (int j = 0; j < 2; ++ j) {
				for (int k = 0; k < 2; ++ k) c.a[i][j] = std::max(a[i][k] + b.a[k][j], c.a[i][j]);
			}
		}
		return c;
	}
} a[SIZE];

struct seg {
	int l, r; matrix v;
} t[SIZE << 2];

namespace GTR {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (c < 48 || c > 57) b ^= c == '-', c = fetch();
		while (c >= 48 && c <= 57) a = (a << 1) + (a << 3) + c - 48, c = fetch();
		return b ? a : -a;
	}
} using GTR::read;

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

void dfs1(int u, int anc) {
	siz[u] = 1, f[u][1] = w[u];
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == anc) continue;
		fa[v] = u, dep[v] = dep[u] + 1;
		dfs1(v, u); siz[u] += siz[v];
		if (siz[v] > siz[son[u]]) son[u] = v;
		f[u][1] += f[v][0], f[u][0] += std::max(f[v][0], f[v][1]);
	}
}

void dfs2(int u, int top) {	
	dfn[u] = ++ tim, idx[tim] = u, bel[u] = top, edp[top] = dfn[u];
	a[u].a[1][0] = w[u], a[u].a[1][1] = -inf;
	if (son[u]) dfs2(son[u], top);
	for (int i = head[u], v; i; i = edge[i].nxt) {
		v = edge[i].to;
		if (v == son[u] || v == fa[u]) continue;
		dfs2(v, v);
		a[u].a[0][0] += std::max(f[v][0], f[v][1]);
		a[u].a[1][0] += f[v][0];
	}
	a[u].a[0][1] = a[u].a[0][0];
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1
#define pushUp(p) (t[p].v = t[lson(p)].v * t[rson(p)].v)

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) return t[p].v = a[idx[l]], void();
	int mid = (l + r) >> 1;
	build(lson(p), l, mid), build(rson(p), mid + 1, r);
	pushUp(p);
}

void modify(int p, int pos) {
	if (t[p].l == t[p].r) return t[p].v = a[idx[t[p].l]], void();
	int mid = (t[p].l + t[p].r) >> 1;
	if (pos <= mid) modify(lson(p), pos);
	else modify(rson(p), pos);
	pushUp(p);
}

matrix query(int p, int l, int r) {
	if (l <= t[p].l && t[p].r <= r) return t[p].v;
	int mid = (t[p].l + t[p].r) >> 1; 
	if (r <= mid) return query(lson(p), l, r);
	else if (mid < l) return query(rson(p), l, r);
	return query(lson(p), l, r) * query(rson(p), l, r);
}

void modifyDP(int u, int val) {
	a[u].a[1][0] += val - w[u], w[u] = val;
	while (u) {
		matrix lst = query(1, dfn[bel[u]], edp[bel[u]]);
		modify(1, dfn[u]);
		matrix cur = query(1, dfn[bel[u]], edp[bel[u]]);
		u = fa[bel[u]];
		a[u].a[0][0] += std::max(cur.a[0][0], cur.a[1][0]) - std::max(lst.a[0][0], lst.a[1][0]);
		a[u].a[0][1] = a[u].a[0][0], a[u].a[1][0] += cur.a[0][0] - lst.a[0][0];
	}
}

int main() {
	n = read(), m = read();
	for (int i = 1; i <= n; ++ i) w[i] = read();
	for (int i = 1, u, v; i < n; ++ i) {
		u = read(), v = read();
		addEdge(u, v), addEdge(v, u);
	}
	dfs1(1, 0), dfs2(1, 1);
	build(1, 1, n);
	int u, val; matrix ans;
	while (m --) {
		u = read(), val = read(); modifyDP(u, val);
		ans = query(1, 1, edp[1]);
		printf("%d\n", std::max(ans.a[0][0], ans.a[1][0]));
	}
	return 0;
}
```

## 你以为这就完了?

你以为这就完了?

新定义了之后的矩阵乘法乘的范围是固定的,一定不能乘出去了,不然会爆毙.平常矩阵乘法随便写都对,那是因为加法乘法跟 $0$ 这种初始值怎么搞都没事. `min` 或 `max` 就有很大的关系.

再者,一定要注意,有的东西是严格从链底贡献到链顶的,矩阵乘法不满足交换律,所以线段树结合的地方应该写 $t[rs] * t[ls]$ 之类的.

假如遇到奇奇怪怪的错误,先开个 `long long` 再来找我

最后修改：2021 年 10 月 13 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

暴力膜托
暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托暴力膜托%%%
TosakaUCW
前排狂暴膜托！
菲兹克斯喵
竟然……又找到一个校友……而且初中和高中都是同一个学校……天哪...
暴力膜托
快给黄明珍开个方子吧，可怜孩子补太猛了
Yanws
牢师求更新

动态DP 学习笔记

tony102 • 2021 年 06 月 10 日

## 常见形式

动态DP 常用于解决树形DP 带点相关的东西的修改, 并询问每次修改(可永久可不永久)后的 DP 结果.

## 矩阵的结合律以及运算的结合律

最重要的一点就是利用两者的可结合来维护 DP

首先什么样的东西满足结合律?  例如加法和乘法: $(A + B) + C = A + (B + C)$ , $(AB) \times C = A \times (BC)$

把加法和乘法混在一起,是否还满足结合律? 也就是分配律: $A \times (B + C) = AB + AC = AC + AB$

为什么要在最后加上 $AC + AB$ ? 因为一个可以分配的东西内部必须可以满足交换律,这样结合相乘的东西交换才也能满足分配律.

满足结合律,有两个条件,上面已经介绍清楚了,现在提炼一下:

1. 运算 $A$ 对内部运算 $B$ 有分配律
2. 运算 $A, B$ 都有交换律

我们一般 DP 的 $min, max, +, \times$ 都是有结合律的.

## 具体方法

知道矩阵的运算可以结合后怎么套到树链剖分上来呢? 以 [Luogu4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) 为例,详细介绍

我们先设出不带修改求最大权独立集的树形 DP 方程, 设 $f_{u,0/1}$ 表示选或不选 $u$ 节点的最大权, 转移:

$$
\left\{
\begin{aligned}
f_{u,0}& = \sum_{v \in son(u)} max(f_{v,0}, f_{v,1}) \\
f_{u,1} & = w_u + \sum_{v \in son(u)} f_{v,0}
\end{aligned}
\right.
$$

$$
\left\{
\begin{aligned}
f_{u,0}& = g_{u,0} + max(f_{heavyson(u), 0}, f_{heavyson(u), 1}) \\
f_{u,1} & = g_{u,1} + f_{heavyson(u), 0}
\end{aligned}
\right.
$$

来谈谈怎么快速构造出来,首先我们要的答案可以先写成一个方便的列向量

$$
\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix}
$$

$$
\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix} = \begin{bmatrix} g_{i,0} & g_{i,0} \\ g_{i,1} & -\infty\end{bmatrix} \times \begin{bmatrix} f_{heavyson,0} \\ f_{heavyson,1} \end{bmatrix}
$$

在这个新定义的矩阵乘法中 $f_{i,0} = max(g_{i,0} + f_{heavyson, 0}, g_{i,0} + f_{heavyson,1})$  因为满足结合律, 很明显 $g_{i,0}$ 在里在外都不影响运算的结果.

现在已经知道了如何在线段树上结合维护,还需要考虑每次怎么改.

放了代码就算结束了吧

```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e5 + 5, MAT = 5;
const int inf = 1e9;

int n, m, tim, num;
int w[SIZE], fa[SIZE], dep[SIZE];
int head[SIZE], dfn[SIZE], idx[SIZE], bel[SIZE], edp[SIZE], siz[SIZE], son[SIZE], f[SIZE][2], g[SIZE][2];

struct node {
	int to, nxt;
} edge[SIZE << 1];

struct matrix {
	int a[MAT][MAT];
	
	void clear() { memset(a, 0, sizeof(a)); }

struct seg {
	int l, r; matrix v;
} t[SIZE << 2];

void addEdge(int u, int v) {
	edge[++ num] = (node) {v, head[u]}, head[u] = num;
}

#define lson(p) p << 1
#define rson(p) p << 1 | 1
#define pushUp(p) (t[p].v = t[lson(p)].v * t[rson(p)].v)

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) return t[p].v = a[idx[l]], void();
	int mid = (l + r) >> 1;
	build(lson(p), l, mid), build(rson(p), mid + 1, r);
	pushUp(p);
}

## 你以为这就完了?

你以为这就完了?

再者,一定要注意,有的东西是严格从链底贡献到链顶的,矩阵乘法不满足交换律,所以线段树结合的地方应该写 $t[rs] * t[ls]$ 之类的.

假如遇到奇奇怪怪的错误,先开个 `long long` 再来找我

动态DP 学习笔记

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

名人传

VP: AtCoder Beginner Contest 222(ABC222)

写在 CSP-S2021 前

机房标准化岚语发音对照

VP: AtCoder Beginner Contest 221(ABC221)

Leveraging CORAL-Correlation Consistency Network for Semi-Supervised Left Atrium MRI Segmentation

动态DP 学习笔记

Luogu5308 [COCI2019] Quiz

CF1437D Minimal Height Tree

VP: AtCoder Beginner Contest 217 (ABC217)

动态DP 学习笔记

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

动态DP 学习笔记

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款