动态 DP 学习笔记

动态 DP 在 NOIP2018D2T3 考察后风靡 OI 圈，然而我却一直没学。

引入

考虑这样一个问题：

给定一棵 $n$ 个点的树，点有点权 $w_i$。
有 $m$ 次操作，每次操作给定 $x,y$，表示将 $w_x$ 修改为 $y$。
每次操作后，询问这棵树的最大权独立集的权值大小。
$n,m \le 10^5$。

如果只有一次询问，我们显然可以用这样一个简单地树形 dp 解决：

设根为 $rt$。

设 $f_{i,0/1}$ 表示 $i$ 点不选/选时，$i$ 的子树内的最大答案。

转移为：

$$\begin{cases}f_{x,0} = \sum_{y \in son_x} \max(f_{y,0}, f_{y,1}) \\\\f_{x,1} = w_x + \sum_{y \in son_x} f_{y,0}\end{cases}$$

目标为 $\max(f_{rt,0}, f_{rt,1})$。

多次询问呢？

这时候就需要可以解决树上带修 DP 问题的算法，也就是动态 DP。

动态 DP

广义矩阵乘法

定义广义矩阵乘法 $A \times B = C$ 为： $$C_{i,j} = \max_{k=1}^{n}(A_{i,k} + B_{k,j})$$ 即，将普通矩阵乘法中的乘法变成加法，加法变成取 $\max$。

同时，广义矩阵乘法满足结合律，所以可以使用矩阵快速幂。

动态 DP

首先进行树链剖分，设 $h_i$ 表示 $i$ 的重儿子。

设 $g_{i,0/1}$ 表示不选择/选择 $i$，同时只选择 $i$ 的轻儿子所在的子树的最大答案。

则有转移： $$\begin{cases}g_{x,0} = \sum_{y \in son_x, y \ne h_i} \max(f_{y,0}, f_{y,1}) \\\\g_{x,1} = w_x + \sum_{y \in son_x, y \ne h_i} f_{y,0} \\\\f_{x,0} = g_{x,0} + \max(f_{h_x, 0}, f_{h_x, 1}) \\\\f_{x,1} = g_{x,1} + f_{h_x,0}\end{cases}$$ 目标同样为 $\max(f_{rt,0}, f_{rt,1})$。

注意，这个转移是先计算 $g$ 后计算 $f$ 的，因此我们需要先处理轻儿子，然后处理重儿子。

考虑用线段树维护每条链的 dp 值，这样我们就可以单次 $\mathcal O(\log^2 n)$ 修改并回答询问了。

如何维护呢？

观察 $f$ 的转移，可以发现它等价于广义矩阵乘法的转移形式： $$\begin{bmatrix}g_{i,0} & g_{i,0}\\\\g_{i,1} & -\infty\end{bmatrix}\times \begin{bmatrix}f_{h_i,0} & 0\\\\f_{h_i,1} & 0\end{bmatrix}=\begin{bmatrix}f_{i,0} & 0\\\\f_{i,1}& 0\end{bmatrix}$$

因此，对于每个点，我们维护矩阵 $\begin{bmatrix}g_{i,0} & g_{i,0}\\\\g_{i,1} & -\infty\end{bmatrix}$，则一条链的链顶的 $\begin{bmatrix}f_{i,0} & 0\\\\f_{i,1}& 0\end{bmatrix}$，就等于这条链上的矩阵从上到下相乘后的矩阵。

于是，我们用线段树维护矩阵 $\begin{bmatrix}g_{i,0} & g_{i,0}\\\\g_{i,1} & -\infty\end{bmatrix}$ 的连乘积就可以了。

【模板】P4719 【模板】动态 DP

const int N = 1e5 + 7, inf = 1e9;
int n, m, w[N], d[N], f[N], s[N], son[N];
int dfn[N], rnk[N], top[N], pot[N], num, F[N][2], G[N][2];
vi e[N];
struct mat {
	int a[2][2];
	inline mat() { memset(a, 0, sizeof(a)); }
	inline friend mat operator * (mat a, mat b) {
		mat c;
		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] = max(c.a[i][j], a.a[i][k] + b.a[k][j]);
		return c;
	}
} g[N];
struct T {
	int l, r;
	mat a;
} t[N<<2];

void dfs(int x) {
	s[x] = 1, F[x][1] = w[x];
	for (int y : e[x])
		if (y != f[x]) {
			f[y] = x, d[y] = d[x] + 1;
			dfs(y), s[x] += s[y];
			if (s[y] > s[son[x]]) son[x] = y;
			F[x][0] += max(F[y][0], F[y][1]);
			F[x][1] += F[y][0];
		}
}

void dfs(int x, int p) {
	dfn[x] = ++num, rnk[num] = x;
	top[x] = p, pot[p] = x;
	G[x][1] = w[x];
	if (son[x]) dfs(son[x], p);
	for (int y : e[x])
		if (y != f[x] && y != son[x]) {
			dfs(y, y);
			G[x][0] += max(F[y][0], F[y][1]);
			G[x][1] += F[y][0];
		}
}

void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	if (l == r) return t[p].a = g[rnk[l]], void();
	build(ls, l, md), build(rs, md + 1, r);
	t[p].a = t[ls].a * t[rs].a;
}

void mdf(int p, int x) {
	if (t[p].l == t[p].r) return t[p].a = g[rnk[x]], void();
	mdf(x <= md ? ls : rs, x);
	t[p].a = t[ls].a * t[rs].a;
}

mat ask(int p, int l, int r) {
	if (t[p].l >= l && t[p].r <= r) return t[p].a;
	if (r <= md) return ask(ls, l, r);
	if (l > md) return ask(rs, l, r);
	return ask(ls, l, r) * ask(rs, l, r);
}

inline void change(int x, int y) {
	g[x].a[1][0] += y - w[x], w[x] = y;
	while (x) {
		mat lst = ask(1, dfn[top[x]], dfn[pot[top[x]]]);
		mdf(1, dfn[x]);
		mat now = ask(1, dfn[top[x]], dfn[pot[top[x]]]);
		x = f[top[x]];
		int o = max(now.a[0][0], now.a[1][0]) - max(lst.a[0][0], lst.a[1][0]);
		g[x].a[0][0] = g[x].a[0][1] += o;
		g[x].a[1][0] += now.a[0][0] - lst.a[0][0];
	}
}

int main() {
	rd(n), rd(m), rda(w, n);
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	for (int i = 1; i <= n; i++)
		reverse(e[i].begin(), e[i].end()); 
	d[1] = 1, dfs(1), dfs(1, 1);
	for (int i = 1; i <= n; i++)
		g[i].a[0][0] = g[i].a[0][1] = G[i][0],
		g[i].a[1][0] = G[i][1], g[i].a[1][1] = -inf;
	build(1, 1, n);
	for (int i = 1, x, y; i <= m; i++) {
		rd(x), rd(y), change(x, y);
		mat ans = ask(1, 1, dfn[pot[1]]);
		print(max(ans.a[0][0], ans.a[1][0]));
	}
	return 0;
}

参考资料

• OI Wiki 动态 DP
• shadowice1984 题解 P4643 【模板】动态dp