動態DP學習筆記
學習了一下動態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模板題了。