动态DP,ddp

动态DP?动态动态规划?

个人理解:动态DP,就是普通DP加修改操作,然后就变成了个毒瘤题。

直接就着例题写吧。

例题

P4719 【模板】"动态 DP"&动态树分治

求树上最大独立集。要求支持修改点权。n<=1e5.

算法原理

首先不带修的最大独立集是一个NOIP题:

\(f[cur][0/1]\) 表示 \(cur\) 选/不选 其子树内(含 \(cur\))的被选点权值和。

\[f[cur][0]= \sum max(f[to][0], f[to][1]) \]

\[f[cur][1] = \sum f[to][0] \]

既然要求支持修改,我们可以拿出对付树的利器:树链剖分。将树剖分成重链和轻边。然后 \(f[cur][0/1]\) 含义不变,另设 \(g[cur][0/1]\) 表示不考虑重儿子的 \(f\)。那么有:

\[g[cur][0]= \sum max(g[to][0], g[to][1]) \]

\[g[cur][1] = \sum g[to][0] \]

为了描述方便,规定 \(i + 1\) 为在重链上与 \(i\) 相邻的比 \(i\) 深的那个点。则:

\[f[i][0] = g[i][0] + max(f[i + 1][0], f[i + 1][1]) \]

\[f[i][1] = g[i][1] + f[i + 1][0] \]

然后我们发现这样老是[0][1]不方便,直接用 \(2×1\) 的矩阵来表示 \(f, g\),这样的话,我们就发现 \(f\) 矩阵可以由与 \(g\) 有关的矩阵递推:

\[\begin{bmatrix} g_{i,0} & g_{i, 0}\\ g_{i, 1} & -\infty\end{bmatrix} × \begin{bmatrix} f_{i+1, 0} \\ f_{i+1, 1} \end{bmatrix}=\begin{bmatrix} f_{i,0} \\ f_{i,1} \end{bmatrix}\]

这样,我们就只用维护每个点的 \(g\) 矩阵,用到 \(f\) 的时候直接拿 \(g\) 矩阵乘一下即可。这个 \(g\) 矩阵是重链上的一堆矩阵,因此我们可以拿线段树维护。

现在考虑修改带来的影响

如果我们修改了某一个点的权值,那么这个点的 \(g\) 矩阵将会改变,不过重链上的其它 \(g\) 矩阵不会改变。但是,重量顶端的父亲的 \(g\) 矩阵会因为重链上的 \(f\) 的改变而改变,因此我们需要修改重链父亲的 \(g\) 矩阵,以及重链父亲所在重链的顶端的父亲的 \(g\) 矩阵...

流程大概是:修改 \(cur\) 的 \(g\) 矩阵,计算 \(top\) 的 \(f\),(如果 \(cur\) 尚不为树根),cur = fa[top[cur]],重复。

代码实现

具体实现的时候,我们自然可以严格按照流程的做法来。不过,相比树剖疯狂跳 \(fa[top]\),LCT的 \(Access\) 函数也可以较为轻松地实现这种操作,并且LCT可以将信息直接维护到点上,避开线段树无比笨拙的修改查询操作,砍掉一个 \(log\),而且还不用 \(makeroot\),因此不用 \(pushr,pushdown\),是为数不多的LCT比树剖好写的题。所以,这题用LCT维护原图子树信息是个不错的选择。

还有一些简化代码的小 trick:

  1. 一开始可以让所有边都为虚边,直接一遍DFS计算出所有 \(g\) 矩阵。

  2. 我们保持1为根节点不变;所有矩阵都可以开成 2×2 的矩阵。这是因为我们矩阵初始化全为 -inf,如果真的要拿一个 2×2 的矩阵和 2×1 的矩阵乘,由于 2×1 矩阵的第二列全为 -inf,最终结果的第二列也将是 -inf,并不会影响答案。

  3. 最终统计答案的时候,可以直接 \(splay(1)\) 然后就拿 1 节点的 \(mul\) 计算答案。本来应该是 1 所在的实链的底端的那个 \(f\) 矩阵乘其它的 \(g\) 矩阵,但是我们发现底端 \(g\) 矩阵的第一列恰好是 \(f\) 矩阵的第一列,因此乘出来的第一列就恰好是答案。

关键代码

略微感受到shadowice大佬考场调bug的感觉了,我还是刚学完ddp,理清思路再写,还写出了五个bug。

int h[N];
matrix val[N], mul[N];
int son[N][2], fa[N];
inline void pushup(int cur) {
	mul[cur] = val[cur];
	int ls = son[cur][0], rs = son[cur][1];
	if (ls)	mul[cur] = mul[ls] * mul[cur];
	if (rs)	mul[cur] = mul[cur] * mul[rs];
}
inline void Access(int cur) {
	for (register int p = cur, lst = 0; p; lst = p, p = fa[p]) {
		splay(p);//Attention!
		if (lst) {
			val[p].h[0][0] -= max(mul[lst].h[0][0], mul[lst].h[1][0]);//Attention!!! : mul
			val[p].h[1][0] -= mul[lst].h[0][0];//Attention!!! : mul
		}
		int rs = son[p][1];
		if (rs) {
			val[p].h[0][0] += max(mul[rs].h[0][0], mul[rs].h[1][0]);//Attention!!!
			val[p].h[1][0] += mul[rs].h[0][0];//Attention!!!
		}
		val[p].h[0][1] = val[p].h[0][0];
		son[p][1] = lst;
		pushup(p);
	}
}
int g[N][2];
void dfs(int cur, int faa) {
	g[cur][1] = h[cur]; fa[cur] = faa;
	for (register int i = head[cur]; i; i = e[i].nxt) {
		int to = e[i].to; if (to == faa)	continue;
		dfs(to, cur);
		g[cur][0] += max(g[to][0], g[to][1]);
		g[cur][1] += g[to][0];
	}
	val[cur].h[0][0] = val[cur].h[0][1] = g[cur][0];
	val[cur].h[1][0] = g[cur][1];//Attention!
	mul[cur] = val[cur];
}


inline void modify(int cur, int v) {
	Access(cur), splay(cur);
//	val[cur].h[0][0] += v - h[cur];
//	val[cur].h[0][1] = val[cur].h[0][0];
	val[cur].h[1][0] += v - h[cur];//Attention!!!
	h[cur] = v;//Attention!
	pushup(cur);
}

int main() {
	dfs(1, 0);
	while (m--) {
		modify(x, v);
		splay(1);
		ans = max(mul[1].h[0][0], mul[1].h[1][0]);
	}
}
上一篇:pytorch的DP和DDP


下一篇:PyTorch分布式训练详解教程 scatter, gather & isend, irecv & all_reduce & DDP