差别

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

--- 2020-2021:teams:legal_string:jxm2001:动态dp [2021/02/18 20:25]
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$ 为递推式的相关项。
+用于解决一些 $\text{dp}$ 递推式简单但需要支持修改的问题，时间复杂度为 $O(nk^3\log n)$，其中 $k$ 为递推式的相关项。
 ===== 例题一 =====
+[[https://codeforces.com/contest/1380/problem/F|CF1380F]]
+==== 题意 ====
+给定一个长度为 $n$ 的十进制数 $D$。
+设 $a_i$ 表示 $A$ 从低到高的第 $i$ 位，其他定义类同。$A+B$ 表示字符串 $\{a_n+b_n\cdots a_2+b_2,a_1+b_1\}$。
+例如 $3248+908=\{3+0,2+9,4+0,8+8\}=\{3,11,4,16\}=311416$。
+接下来 $q$ 次修改，每次修改 $D$ 的某一位，问每次修改后有多少组 $(A,B)$ 满足 $A+B=D$。
+==== 题解 ====
+从低位到高位考虑 $\text{dp}$。设 $\text{dp}(i)$ 表示 $A+B=D[1,i]$ 的方案数。
+若 $d_i$ 不是通过进位得到的，则有 $\text{dp}(i)\gets (d_i+1)\text{dp}(i-1)$。
+若 $d_i$ 是通过进位得到的，则有 $\text{dp}(i)\gets [10\le d_id_{i-1}\le 18](19-d_id_{i-1})\text{dp}(i-2)$。
+于是有状态转移方程
+$$
+\begin{bmatrix}(d_i+1) & [10\le d_id_{i-1}\le 18](19-d_id_{i-1}) \\1 & 0  \\ \end{bmatrix}
+\begin{bmatrix}\text{dp}(i-1)\\ \text{dp}(i-2)\end{bmatrix}
+=\begin{bmatrix}\text{dp}(i)\\ \text{dp}(i-1)\end{bmatrix}
+$$
+注意每次更新需要更新 $i,i+1$ 两个位置的矩阵，另外把 $d_0$ 设置成 $19$ 防止影响位置 $1$ 的矩阵。另外初始值为
+$$
+\begin{bmatrix}\text{dp}(0)\\ \text{dp}(-1)\end{bmatrix}
+=\begin{bmatrix}1\\ 1\end{bmatrix}
+$$
+最后还有一点：矩阵乘法不满足交换律，而我们是从左往右 $\text{dp}$，所以线段树 $\text{push_up}$ 的时候需要用右区间矩阵乘上左区间矩阵。
+总时间复杂度 $O(q\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5,Mod=998244353;
+struct Matrix{
+	int val[2][2];
+	Matrix(){
+		_for(i,0,2)_for(j,0,2)
+		val[i][j]=0;
+	}
+	Matrix(int a,int b){
+		val[0][0]=a+1;
+		val[0][1]=(10<=b&&b<=18)?19-b:0;
+		val[1][0]=1;
+		val[1][1]=0;
+	}
+	Matrix operator * (const Matrix &b)const{
+		Matrix c;
+		_for(i,0,2)_for(j,0,2)_for(k,0,2)
+		c.val[i][j]=(c.val[i][j]+1LL*val[i][k]*b.val[k][j])%Mod;
+		return c;
+	}
+}s[MAXN<<2];
+int a[MAXN],lef[MAXN<<2],rig[MAXN<<2];
+char buf[MAXN];
+void push_up(int k){
+	s[k]=s[k<<1|1]*s[k<<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(a[M],a[M]*10+a[M-1]);
+		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(a[pos],a[pos]*10+a[pos-1]);
+		return;
+	}
+	int mid=lef[k]+rig[k]>>1;
+	if(mid>=pos)
+	update(k<<1,pos);
+	else
+	update(k<<1|1,pos);
+	push_up(k);
+}
+int main()
+{
+	int n=read_int(),q=read_int();
+	scanf("%s",buf+1);
+	a[0]=19;
+	_rep(i,1,n)a[i]=buf[n+1-i]-'0';
+	build(1,1,n);
+	while(q--){
+		int pos=n+1-read_int(),d=read_int();
+		a[pos]=d;
+		update(1,pos);
+		if(pos<n)update(1,pos+1);
+		enter((s[1].val[0][0]+s[1].val[0][1])%Mod);
+	}
+	return 0;
+}
+</code>
+</hidden>
+===== 例题二 =====
+[[https://www.luogu.com.cn/problem/SP1716|SP1716]]
 ==== 题意 ====
@@ 行 49: / 行 161: @@
 \begin{bmatrix}f(0)\\g(0)\\0\end{bmatrix}
 =\begin{bmatrix}0\\-\infty\\0\end{bmatrix}
+\text{或}\begin{bmatrix}-\infty\\-\infty\\0\end{bmatrix}
 $$
+ps. 这题从左往右 $\text{dp}$ 和从右往左 $\text{dp}$ 状态转移完全相同，所以 $\text{push_up}$ 写反也不影响正确性，但要注意 $\text{query}$ 和 $\text{push_up}$ 的一致性。
 <hidden 查看代码>
@@ 行 74: / 行 189: @@
 int a[MAXN],lef[MAXN<<2],rig[MAXN<<2];
 void push_up(int k){
-	s[k]=s[k<<1]*s[k<<1|1];
+	s[k]=s[k<<1|1]*s[k<<1];
 }
 void build(int k,int L,int R){
@@ 行 105: / 行 220: @@
 	else if(mid<L)return query(k<<1|1,L,R);
 	else
-	return query(k<<1,L,R)*query(k<<1|1,L,R);
+	return query(k<<1|1,L,R)*query(k<<1,L,R);
 }
 int main()
@@ 行 121: / 行 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

用户工具

站点工具

差别

页面工具