差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:jxm2001:动态dp [2021/02/19 10:20]
jxm2001 [题解]
+++ 2020-2021:teams:legal_string:jxm2001:动态dp [2021/02/19 17:40] (当前版本)
jxm2001
@@ 行 1: / 行 1: @@
-====== 动态 dp ======
+====== 动态 DP ======
 用于解决一些 $\text{dp}$ 递推式简单但需要支持修改的问题，时间复杂度为 $O(nk^3\log n)$，其中 $k$ 为递推式的相关项。
@@ 行 40: / 行 40: @@
 $$
-最后还有一点：矩阵乘法不满足交换律，线段树 $\text{push_up}$ 的时候需要用右区间矩阵乘上左区间矩阵。
+最后还有一点：矩阵乘法不满足交换律，而我们是从左往右 $\text{dp}$，所以线段树 $\text{push_up}$ 的时候需要用右区间矩阵乘上左区间矩阵。
 总时间复杂度 $O(q\log n)$。
@@ 行 163: / 行 163: @@
 \text{或}\begin{bmatrix}-\infty\\-\infty\\0\end{bmatrix}
 $$
+ps. 这题从左往右 $\text{dp}$ 和从右往左 $\text{dp}$ 状态转移完全相同，所以 $\text{push_up}$ 写反也不影响正确性，但要注意 $\text{query}$ 和 $\text{push_up}$ 的一致性。
 <hidden 查看代码>
@@ 行 234: / 行 236: @@
 			enter(max(p.val[1][0],p.val[1][2]));
 		}
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 例题三 =====
+[[https://www.luogu.com.cn/problem/P4719|洛谷p4719]]
+==== 题意 ====
+给定一棵点权树，每次修改一个点的点权后查询最大权独立集。
+==== 题解 ====
+首先考虑不带修的情况，设 $f(u,0/1)$ 表示不选择/选择 $u$ 时 $u$ 的子树的最大独立集，于是有
+$$
+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)
+$$
+然后考虑怎么将树型 $\text{dp}$ 转化为序列 $\text{dp}$，很容易想到用仅用重儿子进行转移。
+设 $g(u,0/1)$ 表示删除重儿子及其子树后不选择/选择 $u$ 时 $u$ 的子树的最大独立集。记 $u$ 的重儿子为 $h$，于是有
+$$
+f(u,0)=\max(f(h,0),f(h,1))+g(u,0)\\
+f(u,1)=f(h,0)+g(u,1)\\
+\begin{bmatrix}g(u,0) & g(u,0) \\g(u,1) & -\infty  \\ \end{bmatrix}
+\begin{bmatrix}f(h,0)\\ f(h,1)\end{bmatrix}
+=\begin{bmatrix}f(u,0)\\ f(u,1)\end{bmatrix}
+$$
+重链的末端点均为叶子结点，于是要查询 $f(u,0/1)$，只需要查询 $u$ 到 $u$ 所在重链末端点的叶子结点所代表的矩阵的乘积即可。
+对于叶子结点，有
+$$
+\begin{bmatrix}f(h,0)\\ f(h,1)\end{bmatrix}
+=\begin{bmatrix}0\\ 0\end{bmatrix}
+$$
+于是每次查询的时间复杂度为 $O(\log n)$。而对于修改操作，只需要维护所有 $g(u,0/1)$ 即可。
+$$
+g(u,0)=\sum_{v\in son(u)}^{v\neq h}\max(f(v,0),f(v,1))\\
+g(u,1)=w_u+\sum_{v\in son(u)}^{v\neq h}f(v,0)
+$$
+对 $u$ 的权值进行修改，只会影响 $u$ 的所有祖先结点的 $f$ 值，而重链上子节点的 $f$ 对祖先结点的 $g$ 不产生贡献。
+于是每次只需要更新 $u$ 到根节点路径上所有轻边的父结点的 $g$ 即可，共 $O(\log n)$ 个父结点。
+而更新 $g$ 只需要查询轻边对应的子节点的新旧 $f$ 值，然后减去旧值贡献再补上新值贡献即可，于是每次修改总复杂度 $O(\log^2 n)$。
+需要注意儿子结点编号比父结点大，所以对应线段树上是从右向左转移，所以 $\text{push_up,query}$ 用左区间乘以右区间即可。
+总时间复杂度 $O(q\log^2n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=1e5+5,Inf=1e9;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int w[MAXN],sz[MAXN],f[MAXN],dfn[MAXN],invd[MAXN],dfs_t;
+int h_son[MAXN],mson[MAXN],p[MAXN],dson[MAXN],dp[2][MAXN],g[2][MAXN];
+struct Matrix{
+	int val[2][2];
+	Matrix(){
+		_for(i,0,2)_for(j,0,2)
+		val[i][j]=-Inf;
+	}
+	Matrix(int dfn){
+		val[0][0]=val[0][1]=g[0][invd[dfn]];
+		val[1][0]=g[1][invd[dfn]];
+		val[1][1]=-Inf;
+	}
+	Matrix operator * (const Matrix &b)const{
+		Matrix c;
+		_for(i,0,2)_for(j,0,2)_for(k,0,2)
+		c.val[i][j]=max(c.val[i][j],val[i][k]+b.val[k][j]);
+		return c;
+	}
+};
+namespace Tree{
+	Matrix s[MAXN<<2];
+	int lef[MAXN<<2],rig[MAXN<<2];
+	void push_up(int k){
+		s[k]=s[k<<1]*s[k<<1|1];
+	}
+	void build(int k,int L,int R){
+		lef[k]=L,rig[k]=R;
+		int M=L+R>>1;
+		if(L==R){
+			s[k]=Matrix(M);
+			return;
+		}
+		build(k<<1,L,M);
+		build(k<<1|1,M+1,R);
+		push_up(k);
+	}
+	void update(int k,int pos){
+		if(lef[k]==rig[k]){
+			s[k]=Matrix(pos);
+			return;
+		}
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=pos)
+		update(k<<1,pos);
+		else
+		update(k<<1|1,pos);
+		push_up(k);
+	}
+	Matrix query(int k,int L,int R){
+		if(L<=lef[k]&&rig[k]<=R)return s[k];
+		int mid=lef[k]+rig[k]>>1;
+		if(mid>=R)return query(k<<1,L,R);
+		else if(mid<L)return query(k<<1|1,L,R);
+		else
+		return query(k<<1,L,R)*query(k<<1|1,L,R);
+	}
+}
+void dfs_1(int u,int fa){
+	sz[u]=1;f[u]=fa;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==fa)continue;
+		dfs_1(v,u);
+		sz[u]+=sz[v];
+		if(sz[v]>mson[u]){
+			h_son[u]=v;
+			mson[u]=sz[v];
+		}
+	}
+}
+void dfs_2(int u,int top){
+	dfn[u]=++dfs_t;invd[dfs_t]=u;p[u]=top;
+	dson[u]=dfs_t,g[1][u]=w[u];
+	if(mson[u]){
+		dfs_2(h_son[u],top);
+		dson[u]=dson[h_son[u]];
+		dp[0][u]=max(dp[0][h_son[u]],dp[1][h_son[u]]);
+		dp[1][u]=dp[0][h_son[u]];
+	}
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(v==f[u]||v==h_son[u])continue;
+		dfs_2(v,v);
+		g[0][u]+=max(dp[0][v],dp[1][v]);
+		g[1][u]+=dp[0][v];
+	}
+	dp[0][u]+=g[0][u];
+	dp[1][u]+=g[1][u];
+}
+void update(int u,int val){
+	g[1][u]+=val-w[u];
+	w[u]=val;
+	int old_dp[2],new_dp[2];
+	while(u){
+		Matrix m=Tree::query(1,dfn[p[u]],dson[u]);
+		old_dp[0]=max(m.val[0][0],m.val[0][1]);
+		old_dp[1]=max(m.val[1][0],m.val[1][1]);
+		Tree::update(1,dfn[u]);
+		m=Tree::query(1,dfn[p[u]],dson[u]);
+		new_dp[0]=max(m.val[0][0],m.val[0][1]);
+		new_dp[1]=max(m.val[1][0],m.val[1][1]);
+		u=f[p[u]];
+		if(u){
+			g[0][u]=g[0][u]-max(old_dp[0],old_dp[1])+max(new_dp[0],new_dp[1]);
+			g[1][u]=g[1][u]-old_dp[0]+new_dp[0];
+		}
+	}
+}
+int main()
+{
+	int n=read_int(),q=read_int();
+	_rep(i,1,n)w[i]=read_int();
+	_for(i,1,n){
+		int u=read_int(),v=read_int();
+		Insert(u,v);Insert(v,u);
+	}
+	dfs_1(1,0);
+	dfs_2(1,1);
+	Tree::build(1,1,n);
+	while(q--){
+		int u=read_int(),val=read_int();
+		update(u,val);
+		Matrix m=Tree::query(1,dfn[1],dson[1]);
+		enter(max(max(m.val[0][0],m.val[0][1]),max(m.val[1][0],m.val[1][1])));
 	}
 	return 0;

CVBB ACM Team

用户工具

站点工具

差别

页面工具