當前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

动态dp

發布時間：2024/4/11 编程问答 20 豆豆

生活随笔收集整理的這篇文章主要介紹了动态dp 小編覺得挺不錯的,現在分享給大家,幫大家做個參考.

前言

這是今年NOIP前的坑了，當時由于感覺不太會考所以沒先學
然而NOIP考到了
打出GG
現在回來補一波

題目

先拖出模板題，從模板題認識動態dp的一種典型形式
洛谷P4719 【模板】動態dp
題意：
給定一棵n個點的樹，點帶點權
有m次操作，每次操作給定x,y，表示修改點x的權值為y
你需要在每次操作之后求出這棵樹的最大權獨立集的權值大小
數據范圍：
$1≤n,m≤1051\le n,m\le 10^5$

思考

暴力

對于每次操作 $Θ(1)\Theta(1)$ 改權值， $Θ(n)\Theta(n)$ dp求最大權獨立集
$f_{u,0}$ 表示點 $u$ 不選，其子樹的最大權獨立集大小
$f_{u,1}$ 表示點 $u$ 選，其子樹的最大權獨立集大小
$fu,0=∑fa[v]=umax(fv,0,fv,1)fu,1=v[u]+∑fa[v]=ufv,0\begin{aligned} f_{u,0}&=\sum_{fa[v]=u}max(f_{v,0},f_{v,1})\\ f_{u,1}&=v[u]+\sum_{fa[v]=u}f_{v,0} \end{aligned}$

動態dp

動態dp的思想是通過矩乘來進行轉移以達到動態的效果
考慮樹剖
樹剖之后，我們在修改時讓輕兒子暴力轉移給父親（容易發現從下往上最多只有 $O(logn)\mathcal O(logn)$ 次轉移），這樣的話我們就只需要維護每個節點所有兒子對自己值的貢獻，并根據這些值生成一個矩陣，這樣就可以在重鏈上用線段樹進行動態的查詢了

我們先將上述的dp式子進行一些轉化
設 $s o n [u]$ 為樹剖后 $u$ 的重兒子
$fu,0=max(fson[u],0,fson[u],1)+∑fa[v]=u,v≠son[u]max(fv,0,fv,1)fu,1=v[u]+fson[u],0+∑fav=u,v≠son[u]fv,0\begin{aligned} f_{u,0}&=max(f_{son[u],0},f_{son[u],1})+\sum_{fa[v]=u,v\neq son[u]}max(f_{v,0},f_{v,1})\\ f_{u,1}&=v[u]+f_{son[u],0}+\sum_{fa_v=u,v\neq son[u]}f_{v,0} \end{aligned}$
這樣我們直接取不包含重兒子的項作為 $g_{u,0},g_{u,1}$
即
$gu,0=∑fa[v]=u,v≠son[u]max(fv,0,fv,1)gu,1=v[u]+∑fav=u,v≠son[u]fv,0\begin{aligned} g_{u,0}&=\sum_{fa[v]=u,v\neq son[u]}max(f_{v,0},f_{v,1})\\ g_{u,1}&=v[u]+\sum_{fa_v=u,v\neq son[u]}f_{v,0} \end{aligned}$
考慮對于現在有 $f_{son[u],0},f_{son[u],1}$ 如何構造矩陣生成 $f_{u,0},f_{u,1}$
（當然，由于我們要轉移，我們把原來矩陣的加法操作變成max，乘法操作變成加）
容易發現
$∣fson[u],0fson[u],1∣∣gu,0gu,1gu,0?∞∣=∣fu,0fu,1∣\begin{vmatrix} f_{son[u],0} & f_{son[u],1} \end{vmatrix} \begin{vmatrix} g_{u,0} & g_{u,1} \\ g_{u,0} & -\infty \end{vmatrix}= \begin{vmatrix} f_{u,0} & f_{u,1} \end{vmatrix}$
（當然上面的東西都是矩陣）
假設我們樹剖的線段樹中全部存儲了這些矩陣，那么我們在詢問一個點的dp值的時候直接在線段樹中查詢其到葉子的矩陣乘積即可，復雜度 $O(logn)\mathcal O(logn)$
由于
$∣00∣∣gu,0gu,1gu,0?∞∣=∣gu,0gu,1∣\begin{vmatrix} 0 & 0 \end{vmatrix} \begin{vmatrix} g_{u,0} & g_{u,1} \\ g_{u,0} & -\infty \end{vmatrix}= \begin{vmatrix} g_{u,0} & g_{u,1} \end{vmatrix}$
所以查詢完后矩陣的相應位置的值就是我們要求的值

對于修改操作，我們直接暴力更新一個節點的矩陣值，然后不停的跳重鏈頂端，更新其父親，我們發現更新時需要求重鏈頂端的dp值，復雜度 $O(logn)\mathcal O(logn)$ ，然后要做 $O(logn)\mathcal O(logn)$ 次，此外單次修改一個矩陣復雜度 $O(1)\mathcal O(1)$ ，這樣一來總復雜度就是 $O(log2n)\mathcal O(log^2n)$

代碼

#include<cstdio> #include<cctype> #include<cstring> #define rg register typedef long long ll; template<typename T>inline void read(T&x){char cu=getchar();x=0;bool fla=0;while(!isdigit(cu)){if(cu=='-')fla=1;cu=getchar();}while(isdigit(cu))x=x*10+cu-'0',cu=getchar();if(fla)x=-x;} template<typename T>inline void printe(const T x){if(x>=10)printe(x/10);putchar(x%10+'0');} template<typename T>inline void print(const T x){if(x>=0)printe(x);else putchar('-'),printe(-x);} template<typename T>inline T min(const T x,const T y){return x<y?x:y;} template<typename T>inline T max(const T x,const T y){return x>y?x:y;} template<typename T>inline void mind(T&x,const T y){if(x>y)x=y;} template<typename T>inline void maxd(T&x,const T y){if(x<y)x=y;} const int maxn=100001,maxm=200001; int n,m,V[maxn]; int head[maxn],nxt[maxm],tow[maxm],tmp; inline void addb(const int u,const int v) {tmp++;nxt[tmp]=head[u];head[u]=tmp;tow[tmp]=v; } struct Matrix {ll a[2][2];Matrix(){memset(a,0,sizeof(a));a[1][1]=-0x3f3f3f3f3f;}Matrix operator *(const Matrix b)const{Matrix c;for(rg int i=0;i<2;i++)for(rg int j=0;j<2;j++)for(rg int k=0;k<2;k++)maxd(c.a[i][j],b.a[i][k]+a[k][j]);return c;} }; int tid[maxn],tim,top[maxn],fa[maxn],bak[maxn],endd[maxn],son[maxn],size[maxn],dep[maxn]; void dfs1(const int u) {size[u]=1;for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa[u]){dep[v]=dep[u]+1,fa[v]=u;dfs1(v);size[u]+=size[v];if(size[v]>size[son[u]])son[u]=v;}} } void dfs2(const int u) {tid[u]=++tim,bak[tim]=u;endd[top[u]]=tim;if(son[u]){top[son[u]]=top[u];dfs2(son[u]);for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa[u]&&v!=son[u]){top[v]=v;dfs2(v);}}} } int f[maxn][2]; void dfs(const int u) {f[u][1]=V[u];for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa[u]){dfs(v);f[u][0]+=max(f[v][0],f[v][1]);f[u][1]+=f[v][0];}} } const int MAX=262145; int go[maxn]; Matrix irt[MAX]; Matrix upd(const int u) {Matrix x;int g0=0,g1=V[u];for(rg int i=head[u];i;i=nxt[i]){const int v=tow[i];if(v!=fa[u]&&v!=son[u]){g0+=max(f[v][0],f[v][1]);g1+=f[v][0];}}x.a[0][0]=g0,x.a[0][1]=g1,x.a[1][0]=g0,x.a[1][1]=-0x3f3f3f3f3f;return x; } void ini(const int root,const int l,const int r) {if(l==r){irt[root]=upd(bak[l]);go[l]=root;return;}const int mid=(l+r)>>1;ini(root<<1,l,mid),ini(root<<1|1,mid+1,r);irt[root]=irt[root<<1]*irt[root<<1|1]; } void insert(const int root,const int l,const int r,const int wan) {if(l==r)return;const int mid=(l+r)>>1;if(wan<=mid)insert(root<<1,l,mid,wan);else insert(root<<1|1,mid+1,r,wan);irt[root]=irt[root<<1]*irt[root<<1|1]; } Matrix search(const int root,const int l,const int r,const int wanl,const int wanr) {if(wanl==l&&wanr==r)return irt[root];const int mid=(l+r)>>1;if(wanr<=mid)return search(root<<1,l,mid,wanl,wanr);if(wanl>mid)return search(root<<1|1,mid+1,r,wanl,wanr);return search(root<<1,l,mid,wanl,mid)*search(root<<1|1,mid+1,r,mid+1,wanr); } int main() {read(n),read(m);for(rg int i=1;i<=n;i++)read(V[i]);for(rg int i=1;i<n;i++){int u,v;read(u),read(v);addb(u,v),addb(v,u); }dfs1(1);top[1]=1,dfs2(1);dfs(1);ini(1,1,n);for(rg int i=1;i<=m;i++){int x,y;read(x),read(y);irt[go[tid[x]]].a[0][1]+=y-V[x];insert(1,1,n,tid[x]);V[x]=y;while(1){x=top[x];Matrix M=search(1,1,n,tid[x],endd[x]);if(fa[x]){const int F=go[tid[fa[x]]];irt[F].a[0][0]-=max(f[x][0],f[x][1]);irt[F].a[1][0]-=max(f[x][0],f[x][1]);irt[F].a[0][1]-=f[x][0];f[x][0]=M.a[0][0];f[x][1]=M.a[0][1];irt[F].a[0][0]+=max(f[x][0],f[x][1]);irt[F].a[1][0]+=max(f[x][0],f[x][1]);irt[F].a[0][1]+=f[x][0];insert(1,1,n,tid[fa[x]]);}else{f[x][0]=M.a[0][0];f[x][1]=M.a[0][1];}if(x==1)break;x=fa[x];}print(max(f[1][0],f[1][1])),putchar('\n');}return 0; }

總結

非常后悔noip前沒學這個，少了很多分
noip的經歷證明考前學算法并不是一件壞事
這個算法想清楚還是挺清真的（就是寫的時候樹剖細節沒注意到調了好一會兒）
此外這類問題可以通過全局平衡二叉樹優化一個log
以后再更

超強干貨來襲云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的动态dp的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。

动态
DP