Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

[总结] 动态DP学习笔记

YoungNeal 2019-02-10 21:20:00 阅读数:128 评论数:0 点赞数:0 收藏数:0

学习了一下动态DP

问题的来源:
给定一棵 \(n\) 个节点的树,点有点权,有 \(m\) 次修改单点点权的操作,回答每次操作之后的最大带权独立集大小。

首先一个显然的 \(O(nm)\) 的做法就是每次做一遍树形DP(这也是我在noip考场上唯一拿到的部分分),直接考虑如何优化这个东西。

简化一下问题,假如这棵树是一条链,那就变得很简单了,可以直接拿线段树维护矩阵加速。

可是如果每个点不止有一个儿子呢?
我们首先树剖一下。
\(g[i][0]=\sum\limits_{j\in lightson} \max(f[j][0],f[j][1])\)
\(g[i][1]=a[i]+\sum\limits_{j\in lightson} f[j][0]\)
\(g[i][0]\) 表示 \(i\) 的所有轻儿子的 \(\max(f[j][0],f[j][1])\) 之和,\(g[i][1]\) 表示 \(i\) 的所有轻儿子的 \(g[j][0]\) 之和与 \(a[i]\) 的和。

那转移方程就可以改写为 \(f[i][0]=\max(g[i][0]+f[son[i]][0],g[i][0]+f[son[i]][1])\)
\(f[i][1]=g[i][1]+f[son[i]][0]\)

这就可以放在线段树上维护矩阵了。
即每个点维护一个 \(\quad\begin{matrix}g[i][0]&g[i][0]\\-\infty&g[i][1]\end{matrix}\)。然后在线段树上维护连乘积就好。

还有一点就是修改的时候,要一直跳 \(top\),可以这样理解:假设当前更改了点 \(x\) 的点权,那么就会改变 \(f[top[x]]\) 的值,紧接着就会影响 \(g[fa[top[x]]]\) 的值,所以我们要一直向上跳 \(top\) 修改才能维护好。

最后放一下代码:

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using std::min;
using std::max;
using std::swap;
using std::vector;
typedef double db;
typedef long long ll;
#define pb(A) push_back(A)
#define pii std::pair<int,int>
#define all(A) A.begin(),A.end()
#define mp(A,B) std::make_pair(A,B)
const int N=1e5+5;
const int inf=1e9;
#define ls x<<1
#define rs x<<1|1
#define lss ls,l,mid,ql,qr
#define rss rs,mid+1,r,ql,qr
int tot,dfn[N],top[N],end[N];
int n,m,v[N],sze[N],son[N],f[N][2];
int cnt,head[N],g[N][2],fa[N],fs[N];
struct Edge{
int to,nxt;
}edge[N<<1];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
struct Mat{
int a[3][3];
Mat(){memset(a,0xcf,sizeof a);}
friend Mat operator*(Mat x,Mat y){
Mat z;
for(int i=1;i<=2;i++)
for(int k=1;k<=2;k++)
for(int j=1;j<=2;j++)
z.a[i][j]=max(x.a[i][k]+y.a[k][j],z.a[i][j]);
return z;
}
}sum[N<<2],val[N];
int getint(){
int X=0,w=0;char ch=getchar();
while(!isdigit(ch))w|=ch=='-',ch=getchar();
while( isdigit(ch))X=X*10+ch-48,ch=getchar();
if(w) return -X;return X;
}
void dfs(int now){
sze[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(sze[to]) continue;
fa[to]=now;dfs(to);
sze[now]=sze[to];
son[now]=sze[son[now]]>sze[to]?son[now]:to;
}
}
void dfs(int now,int low){
dfn[now]=++tot;top[now]=low;fs[tot]=now;
if(son[now]) dfs(son[now],low);
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
if(dfn[to]) continue;
dfs(to,to);
g[now][0]+=max(f[to][0],f[to][1]);
g[now][1]+=f[to][0];
} if(son[now]) end[now]=end[son[now]];
else end[now]=now;
g[now][1]+=v[now];
f[now][0]=g[now][0]+max(f[son[now]][0],f[son[now]][1]);
f[now][1]=g[now][1]+f[son[now]][0];
}
void pushup(int x){
sum[x]=sum[ls]*sum[rs];
}
void build(int x,int l,int r){
if(l==r) return sum[x]=val[fs[l]],void();
int mid=l+r>>1; build(ls,l,mid),build(rs,mid+1,r);
pushup(x);
}
void init(){
for(int i=1;i<=n;i++)
val[i].a[1][1]=val[i].a[1][2]=g[i][0],val[i].a[2][1]=g[i][1],val[i].a[2][2]=-inf;
build(1,1,n);
}
Mat query(int x,int l,int r,int ql,int qr){
if(ql<=l and r<=qr) return sum[x];
int mid=l+r>>1;
if(qr<=mid) return query(lss);
if(ql>mid) return query(rss);
return query(lss)*query(rss);
}
Mat ask(int x){
return query(1,1,n,dfn[top[x]],dfn[end[x]]);
}
void modify(int x,int l,int r,int ql,int qr){
if(l==r) return sum[x]=val[fs[l]],void();
int mid=l+r>>1;
ql<=mid?modify(lss):modify(rss);
pushup(x);
}
void change(int x,int y){
val[x].a[2][1]+=y-v[x]; v[x]=y;
Mat pre,nxt;
while(x){
pre=ask(x);
modify(1,1,n,dfn[x],dfn[x]);
nxt=ask(x);
x=fa[top[x]];
val[x].a[1][1]+=max(nxt.a[1][1],nxt.a[2][1])-max(pre.a[1][1],pre.a[2][1]);
val[x].a[1][2]=val[x].a[1][1];
val[x].a[2][1]+=nxt.a[1][1]-pre.a[1][1];
}
}
signed main(){
n=getint(),m=getint();
for(int i=1;i<=n;i++) v[i]=getint();
for(int i=1;i<n;i++){
int x=getint(),y=getint();
add(x,y),add(y,x);
} dfs(1),dfs(1,1),init();
while(m--){
int x=getint(),y=getint();
change(x,y);
Mat ans=ask(1);
printf("%d\n",max(ans.a[1][1],ans.a[2][1]));
} return 0;
}

然后两道例题:

BZOJ4712 洪水

题意

给出一棵树,点有点权。多次增加某个点的点权,并在某一棵子树中询问:选出若干个节点,使得每个叶子节点到根节点的路径上至少有一个节点被选择,求选出的点的点权和的最小值。

Sol

还是动态DP。

先把DP式子列出来: \(f[i]=\min(a[i],\sum\limits_{j\in son[i]} f[j])\),然后套路设 \(g[i]=\sum\limits_{j\in lightson[i]} f[j]\),于是 \(f[i]=\min(a[i],g[i]+f[son[i]])\)

又可以写成矩阵相乘的形式:
\[ \begin{matrix}f[son[i]]\\0\end{matrix}\times \begin{matrix}g[i]&a[i]\\\infty&0\end{matrix}=\begin{matrix}f[i]\\0\end{matrix} \]
然后动态DP就行了。

需要注意一点的是在 \(change\) 函数里,\(pre,nxt\) 的矩阵应该是 \(ask(top[x])\) 而不是 \(ask(x)\)

NOIP2018 保卫王国

题意

给出一棵树,点有点权。每次强制选或不选两个节点,求最小权覆盖集。

Sol

首先有个定理:最小权覆盖集=全集-最大权独立集。然后就是luogu模板题了。

版权声明
本文为[YoungNeal]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/YoungNeal/p/10360291.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领