动态 DP

用于解决一些 $\text{dp}$ 递推式简单但需要支持修改的问题，时间复杂度为 $O(nk^3\log n)$，其中 $k$ 为递推式的相关项。

例题一

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)$。

查看代码

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;
}

例题二

SP1716

题意

给定长度为 $n$ 的序列，接下来两种操作：

单点修改
查询区间 $[l,r]$ 的所有连续子序列中的元素和的最大值

题解

首先考虑如何进行 $\text{dp}$ 递推，设 $f(i)$ 表示所有 $[1,i]$ 的后缀的最大元素和，$g(i)$ 表示所有 $[1,i]$ 的连续子序列的最大元素和。

$$ f(i)=\max(f(i-1)+a_i,a_i),g_i=\max(g(i-1),f(i))=\max(f(i-1)+a_i,g(i-1),a_i) $$

考虑用广义矩阵乘法维护转移，线段树要求广义矩阵乘法需要满足结合律。

$$ \begin{equation}\begin{split} (ABC)_{i,j}&=\sum_{k=1}^n (AB)_{i,k}\oplus C_{k,j} \\ &=\sum_{k=1}^n \left(\left(\sum_{t=1}^nA_{i,t}\oplus B_{t,k}\right)\oplus C_{k,j}\right)\\ & =\sum_{k=1}^n\sum_{t=1}^nA_{i,t}\oplus B_{t,k}\oplus C_{k,j}\\ & =\sum_{t=1}^n\left(A_{i,t}\oplus\left(\sum_{k=1}^nB_{t,k}\oplus C_{k,j}\right)\right)\\ & =\sum_{t=1}^nA_{i,t}\oplus (BC)_{t,j}\\ \end{split}\end{equation} $$ 不难发现，为了使得上式成立，应该有 $a\oplus\sum_{i=1}^n b_i=\sum_{i=1}^n a\oplus b_i$。

普通矩阵乘法中 $\sum$ 表示求和，$\oplus$ 表示乘法。本题可以用 $\max$ 代替 $\sum$，$+$ 代替 $\oplus$。

于是有

$$ \begin{bmatrix}a_i & -\infty & a_i \\a_i & 0 & a_i \\-\infty & -\infty & 0 \\ \end{bmatrix} \begin{bmatrix}f(i-1)\\g(i-1)\\0\end{bmatrix} =\begin{bmatrix}f(i)\\g(i)\\0\end{bmatrix} $$

注意查询的初始值和正常 $\text{dp}$ 相同

$$ \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}$ 的一致性。

查看代码

const int MAXN=5e4+5,Inf=1e9;
struct Matrix{
	int val[3][3];
	Matrix(){
		_for(i,0,3)_for(j,0,3)
		val[i][j]=-Inf;
	}
	Matrix(int a){
		val[0][0]=val[0][2]=val[1][0]=val[1][2]=a;
		val[0][1]=val[2][0]=val[2][1]=-Inf;
		val[1][1]=val[2][2]=0;
	}
	Matrix operator * (const Matrix &b)const{
		Matrix c;
		_for(i,0,3)_for(j,0,3)_for(k,0,3)
		c.val[i][j]=max(c.val[i][j],val[i][k]+b.val[k][j]);
		return c;
	}
}s[MAXN<<2];
int a[MAXN],lef[MAXN<<2],rig[MAXN<<2];
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]);
		return;
	}
	build(k<<1,L,M);
	build(k<<1|1,M+1,R);
	push_up(k);
}
void update(int k,int pos,int v){
	if(lef[k]==rig[k]){
		s[k]=Matrix(v);
		return;
	}
	int mid=lef[k]+rig[k]>>1;
	if(mid>=pos)
	update(k<<1,pos,v);
	else
	update(k<<1|1,pos,v);
	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|1,L,R)*query(k<<1,L,R);
}
int main()
{
	int n=read_int();
	_rep(i,1,n)a[i]=read_int();
	build(1,1,n);
	int q=read_int();
	while(q--){
		int type=read_int(),x=read_int(),y=read_int();
		if(type==0)
		update(1,x,y);
		else{
			Matrix p=query(1,x,y);
			enter(max(p.val[1][0],p.val[1][2]));
		}
	}
	return 0;
}

例题三

洛谷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)$。

查看代码

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

目录

动态 DP

例题一

题意

题解

例题二

题意

题解

例题三

题意

题解

CVBB ACM Team

用户工具

站点工具

目录

动态 DP

例题一

题意

题解

例题二

题意

题解

例题三

题意

题解

页面工具