當(dāng)前位置：首頁 > 编程资源 > 编程问答 >内容正文

编程问答

树形DP 学习总结

發(fā)布時(shí)間：2024/1/17 编程问答 34 豆豆

生活随笔收集整理的這篇文章主要介紹了树形DP 学习总结小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.

DP畢竟是算法中最精妙的部分，理解并玩得花哨還是需要一定的時(shí)間積累

之前對(duì)普通的DP也不敢說掌握，只能說略懂皮毛

在學(xué)習(xí)樹形DP 的同時(shí)也算是對(duì)DP有了更深的理解吧

DP的關(guān)鍵就在于狀態(tài)的定義以及找轉(zhuǎn)移

首先要考慮清楚狀態(tài)，狀態(tài)要能夠很好地并且完整地描述子問題

其次考慮最底層的狀態(tài)，這些狀態(tài)一般是最簡單的情況或者是邊界情況

再就是考慮某一個(gè)狀態(tài)能從哪些子狀態(tài)轉(zhuǎn)移過來，同時(shí)還要考慮轉(zhuǎn)移的順序，確保子問題已經(jīng)解決

樹形DP很多時(shí)候就是通過子節(jié)點(diǎn)推父親節(jié)點(diǎn)的狀態(tài)

還是通過題目來加強(qiáng)理解吧

1.HDU 1520

題意：給一棵樹，選最多的結(jié)點(diǎn)使得選擇的結(jié)點(diǎn)不存在直接的父子關(guān)系

很容易想到一個(gè)結(jié)點(diǎn)有兩個(gè)狀態(tài)：選或者不選

所以自然地想到狀態(tài)dp[u][0/1]表示u子樹內(nèi)的最佳答案，u的狀態(tài)為選或者不選

初始化自然是葉子結(jié)點(diǎn)dp[u][0]=0,dp[u][1]=w[u]

轉(zhuǎn)移則可以考慮依次考慮

u不選的時(shí)候：u的兒子可以任意選或者不選，所以dp[u][0]+=max(dp[v][0],dp[v][1])

u選的時(shí)候：u的兒子必定不能選，所以dp[u][1]+=dp[v][0] ? 然后dp[u][1]+=w[u]表示加上u這個(gè)點(diǎn)

答案自然就是max(dp[rt][0],dp[rt][1])了

2.POJ 1436

題意：選中一個(gè)點(diǎn)則與其相連的邊將被覆蓋，問最少選幾個(gè)點(diǎn)使得樹中所有邊均被覆蓋

和上一個(gè)題很類似

同樣狀態(tài)設(shè)為dp[u][0/1]

初始的底層狀態(tài)自然是dp[u][0]=0,dp[u][1]=1;

考慮一個(gè)非葉子結(jié)點(diǎn)和它兒子的所有連邊

如果當(dāng)前結(jié)點(diǎn)不選，那這些邊只能由其兒子保護(hù)，所以dp[u][0]+=dp[v][1]

如果當(dāng)前結(jié)點(diǎn)選，那這些邊已被保護(hù)，其兒子選和不選都行，所以dp[u][1]+=min(dp[v][0],dp[v][1])

答案自然是min(dp[rt][0],dp[rt][1])

3.URAL 1018

題意：樹中每個(gè)點(diǎn)有權(quán)值，問只留下k個(gè)點(diǎn)剩下的最大權(quán)值和是多少？留下的點(diǎn)還是構(gòu)成一棵樹

樹形背包

狀態(tài)定義成dp[u][i]表示u子樹內(nèi)剩i個(gè)點(diǎn)的最大權(quán)值

考慮葉子結(jié)點(diǎn)：dp[u][0]=0,dp[u][1]=w[u]

考慮非葉子結(jié)點(diǎn)的一個(gè)狀態(tài)dp[u][i]，對(duì)于當(dāng)前的一個(gè)兒子v，枚舉一個(gè)k表示從這個(gè)兒子里取幾個(gè)結(jié)點(diǎn)，維護(hù)一個(gè)最大值

其實(shí)我們這里的狀態(tài)是三維的，表示u子樹的前j個(gè)子樹取了i個(gè)結(jié)點(diǎn)的答案

我們使用滾動(dòng)數(shù)組把j這一維滾掉

這里簡化了題目，每一個(gè)結(jié)點(diǎn)固定只有兩個(gè)兒子，用一般做法做肯定也是沒問題的

還有要注意的地方就是這里根是一定要保留的

處理方法就是對(duì)于狀態(tài)dp[u][1]直接賦值，枚舉時(shí)候i從2開始，這樣就可以默認(rèn)根已取

4.HDU 2196

題意：對(duì)于樹中的每一個(gè)結(jié)點(diǎn)，輸出樹中與其距離最遠(yuǎn)的結(jié)點(diǎn)的距離值

經(jīng)典的樹形DP問題

狀態(tài)定義為dp[u][0/1]為u到其子樹內(nèi)結(jié)點(diǎn)的最遠(yuǎn)距離、次遠(yuǎn)距離

這樣一輪dp下來，可以想到對(duì)于根來說,dp[rt][0]就是它的答案

但是對(duì)于其它結(jié)點(diǎn)來說只得到了其子樹內(nèi)的答案，而我們需要的是其對(duì)于整棵樹的信息

這里需要再一次dfs，相當(dāng)于反過來從根往葉子再dp一次，通過根的答案推其余結(jié)點(diǎn)的答案

這里之所以要維護(hù)一個(gè)次大值，就是對(duì)于一個(gè)結(jié)點(diǎn)u的兒子v，

若u的最遠(yuǎn)距離是經(jīng)過u的，那v的答案應(yīng)該是v子樹內(nèi)的答案和u的次大值比較，否則v的答案和u的最大值比較

畫個(gè)圖就明白了

5.POJ 2152

題意：樹中每個(gè)結(jié)點(diǎn)有兩個(gè)值：w[i]表示在i建設(shè)防火設(shè)施的價(jià)格，d[i]表示與i最近的防火設(shè)施的距離上限，求滿足所有d[i]的最小花費(fèi)

算是一道比較難的樹形dp，狀態(tài)和普通的樹形DP略有不同

樹形dp很多時(shí)候是把一個(gè)結(jié)點(diǎn)及其子樹看成一個(gè)整體，然后考慮這個(gè)結(jié)點(diǎn)的狀態(tài)進(jìn)行轉(zhuǎn)移

考慮到數(shù)據(jù)范圍N<=1000,可以定義狀態(tài)dp[u][i]表示u依靠i時(shí)，保證子樹內(nèi)安全的最小花費(fèi)

為了轉(zhuǎn)移方便，再定義all[u]表示保證u的安全的最小花費(fèi)

其實(shí)可以理解為all[u]是在dp[u][i]中取了個(gè)最優(yōu)值

要確定一個(gè)點(diǎn)是否能被u依靠就需要知道u與該點(diǎn)的距離

所以先n^2處理樹中任意兩點(diǎn)的距離

考慮葉子結(jié)點(diǎn)：dp[u][i]=w[i]

考慮一個(gè)非葉子結(jié)點(diǎn)u，先枚舉它依靠的結(jié)點(diǎn)i

再考慮u的兒子v，v可以選擇依靠或者不依靠i，則dp[u][i]+=min(dp[v][i]-c[i],all[v])

對(duì)于u的每一個(gè)i更新u的最優(yōu)解all[u]

對(duì)于u的孫子k是不需要考慮的，因?yàn)閗依靠i的情況在解決v的時(shí)候已經(jīng)考慮到了，所以不會(huì)有重復(fù)計(jì)算的情況

#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #include"bitset" #define LL long long #define ull unsigned long long #define mems(a,b) memset(a,b,sizeof(a)) #define mdzz int mid=(L+R)>>1 #define ls pos<<1 #define rs pos<<1|1 #define lson L,mid,pos<<1 #define rson mid+1,R,pos<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N = 1e3+5; const int M = 2e3+5; const int MOD = 998244353; const int INF = 0x3f3f3f3f;int tot; int first[N]; int dp[N][N],all[N]; int n,u,v,x; int cost[N],d[N],dis[N][N];struct node{int e,next,w;node(){}node(int a,int b,int c):e(a),next(b),w(c){} }edge[M];void init(){tot=0;mems(first,-1);mems(all,INF);mems(dp,INF); }void addedge(int u,int v,int w){edge[tot]=node(v,first[u],w);first[u]=tot++;edge[tot]=node(u,first[v],w);first[v]=tot++; }void dfs1(int rt,int u,int fa){for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dis[rt][v]=dis[rt][u]+edge[i].w;dfs1(rt,v,u);} }void dfs2(int u,int fa){for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dfs2(v,u);}for(int k=1;k<=n;k++) if(dis[u][k]<=d[u]){dp[u][k]=cost[k];for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dp[u][k]+=min(dp[v][k]-cost[k],all[v]);}all[u]=min(all[u],dp[u][k]);} }int T; int main(){//freopen("in.txt","r",stdin);for(int i=0;i<N;i++) dis[i][i]=0;scanf("%d",&T);while(T--){init();scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&cost[i]);for(int i=1;i<=n;i++) scanf("%d",&d[i]);for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&x);addedge(u,v,x);}for(int i=1;i<=n;i++) dfs1(i,i,-1);dfs2(1,-1);printf("%d\n",all[1]);}return 0; } View Code

6.POJ 3162

題意：對(duì)于樹中每一個(gè)結(jié)點(diǎn)i找到另一個(gè)結(jié)點(diǎn)使得兩者距離dp[i]最遠(yuǎn)，最后輸出一段最長區(qū)間的長度，區(qū)間maxv-minv<=M

只是在樹形dp上加了點(diǎn)東西而已，用線段樹+two pointer維護(hù)就好了

#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #include"bitset" #define LL long long #define ull unsigned long long #define mems(a,b) memset(a,b,sizeof(a)) #define mdzz int mid=(L+R)>>1 #define ls pos<<1 #define rs pos<<1|1 #define lson L,mid,pos<<1 #define rson mid+1,R,pos<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N = 1e6+5; const int M = 2e6+5; const int MOD = 998244353; const int INF = 0x3f3f3f3f;int tot; int first[N]; int dp[N][2],id[N][2];struct node{int e,next,w;node(){}node(int a,int b,int c):e(a),next(b),w(c){} }edge[M];void init(){tot=0;mems(first,-1); }void addedge(int u,int v,int w){edge[tot]=node(v,first[u],w);first[u]=tot++;edge[tot]=node(u,first[v],w);first[v]=tot++; }void update(int u){if(dp[u][0]<dp[u][1]){swap(dp[u][0],dp[u][1]);swap(id[u][0],id[u][1]);} }void dfs1(int u,int fa){dp[u][1]=dp[u][0]=0;for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dfs1(v,u);if(edge[i].w+dp[v][0]>dp[u][1]){dp[u][1]=edge[i].w+dp[v][0];id[u][1]=v;}update(u);} }void dfs2(int u,int fa){for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;if(id[u][0]==v){if(dp[u][1]+edge[i].w>dp[v][1]){dp[v][1]=dp[u][1]+edge[i].w;id[v][1]=u;}}else{if(dp[u][0]+edge[i].w>dp[v][1]){dp[v][1]=dp[u][0]+edge[i].w;id[v][1]=u;}}update(v);dfs2(v,u);} }int minv[N<<2],maxv[N<<2];void build(int L,int R,int pos){if(L==R){minv[pos]=maxv[pos]=dp[L][0];return;}mdzz;build(lson);build(rson);minv[pos]=min(minv[ls],minv[rs]);maxv[pos]=max(maxv[ls],maxv[rs]); }int query_min(int l,int r,int L,int R,int pos){if(l<=L&&R<=r) return minv[pos];mdzz;int ans=INF;if(l<=mid) ans=min(ans,query_min(l,r,lson));if(r>mid) ans=min(ans,query_min(l,r,rson));return ans; }int query_max(int l,int r,int L,int R,int pos){if(l<=L&&R<=r) return maxv[pos];mdzz;int ans=-INF;if(l<=mid) ans=max(ans,query_max(l,r,lson));if(r>mid) ans=max(ans,query_max(l,r,rson));return ans; }int n,m,u,v; int main(){//freopen("in.txt","r",stdin);while(~scanf("%d%d",&n,&m)){init();for(int i=2;i<=n;i++){scanf("%d%d",&u,&v);addedge(i,u,v);}dfs1(1,-1);dfs2(1,-1);int ans=0;build(1,n,1);int l=1,r=1;while(1){if(l>r||l>n||r>n) break;int mxv=query_max(l,r,1,n,1);int miv=query_min(l,r,1,n,1);if(mxv-miv<=m){ans=max(ans,r-l+1);r++;}else l++;}printf("%d\n",ans);}return 0; } View Code

7.codeforces 219D

題意：樹邊有方向，選擇一個(gè)點(diǎn)，翻轉(zhuǎn)最少路徑，使得其能到達(dá)其余所有的點(diǎn)，輸出所有可能的答案

可以將翻轉(zhuǎn)理解為一種花費(fèi)，那不翻轉(zhuǎn)就是花費(fèi)0，翻轉(zhuǎn)則為1

可以定義dp[u]表示u到所有點(diǎn)的距離和，那dp[u]最小的就是答案

依舊先考慮u的子樹內(nèi)的答案

考慮一個(gè)葉子：dp[u]=0;

考慮一個(gè)非葉子u以及其的一個(gè)兒子v：很容易想到dp[u]+=dp[v]+w[u,v]

一次dfs下來后rt的答案已知，接下來通過rt來推其余結(jié)點(diǎn)對(duì)于整棵樹的答案

考慮結(jié)點(diǎn)u及其一個(gè)兒子v，v到v子樹內(nèi)的答案已知，v到u除v子樹的結(jié)點(diǎn)的答案是dp[u]-dp[v]-w[u,v]

所以dp[v]+=dp[u]-dp[v]-w[u,v]+w[v,u]

8.POJ 1155

題意：樹中每個(gè)葉子有點(diǎn)權(quán)表示收入，邊權(quán)表示花費(fèi)。選擇某些葉子后，不必要的邊可刪掉，最多選擇幾個(gè)點(diǎn)使得花費(fèi)>=收入

狀態(tài)很多時(shí)候是根據(jù)要求的東西來定義的

這里定義dp[u][i]為子樹u取i個(gè)葉子的最優(yōu)解

由于不選葉子的話是不需要任何花費(fèi)的，所以容易想到dp[u][0]=0

考慮一個(gè)葉子，其第二維只有0/1兩種取值，1的話明顯是dp[u][1]=w[u]

考慮一個(gè)非葉子，第二維1~sz[u]都是無法確定的狀態(tài)，而且考慮到結(jié)果可能是負(fù)值，而且我們需要的是一個(gè)最大值，所以初始化為-INF

對(duì)于一個(gè)結(jié)點(diǎn)u的一個(gè)兒子v，枚舉在這個(gè)兒子中取的葉子數(shù)k，維護(hù)個(gè)最優(yōu)解就好了

9.HDU 1011

題意：樹中每一個(gè)結(jié)點(diǎn)有一個(gè)花費(fèi)一個(gè)收益，問K元能取得的最大收益是多少

明顯的樹形背包，一個(gè)結(jié)點(diǎn)可以看成一個(gè)物品

XJB搞搞就行了

有個(gè)坑是a/20向上取整不能寫成(a-1)/20+1，a可能是0

10.POJ 1947

題意：問最少需要破壞多少條邊能產(chǎn)生一個(gè)大小為K的塊

dp[u][i]表示u的子樹中產(chǎn)生一個(gè)i大小的塊需要破壞的最少邊數(shù)

num[u]表示u的兒子數(shù)

這題考慮的方向不同平常

考慮塊的大小1~sz[u] (0的大小是不合法的狀態(tài))

若要在u的子樹中產(chǎn)生一個(gè)1大小的塊，初始情況應(yīng)該是u和所有兒子的連邊斷開，所以dp[u][1]=num[u]

其實(shí)這樣處理相當(dāng)于對(duì)于每一個(gè)狀態(tài)來說u都是默認(rèn)取了的

考慮一個(gè)結(jié)點(diǎn)u及其一個(gè)兒子v，對(duì)于狀態(tài)dp[u][i] 枚舉在v中取的結(jié)點(diǎn)數(shù)k

最后要枚舉一個(gè)塊的根，因?yàn)槲覀冎疤幚頎顟B(tài)的時(shí)候是默認(rèn)根取，所以最優(yōu)解還可能在子樹中

如果加一維狀態(tài)[0/1]表示u是否取的話應(yīng)該可以避免這個(gè)問題，不過也沒有去嘗試了

11.HDU 1561

題意：每個(gè)結(jié)點(diǎn)有一個(gè)權(quán)值，問選擇K個(gè)結(jié)點(diǎn)（必須按路徑選擇）獲得的最大權(quán)值

典型的樹形背包

由于不是任意選，我們只需要在狀態(tài)轉(zhuǎn)移的時(shí)候變通一下就好了

對(duì)于u來說，我要選擇其子孫的話前提是u選擇

所以對(duì)第二維i==1的時(shí)候單獨(dú)處理，而且之后不再更新這個(gè)值就能保證u是默認(rèn)被選擇的

12.HDU 4003

題意：樹中每條邊有花費(fèi)，有k個(gè)機(jī)器人，問遍歷所有的點(diǎn)的最少花費(fèi)(可以回頭，每次只能從s出發(fā)

這一題的狀態(tài)定義很有意思

dp[u][i]表示遍歷完u的子樹后有i個(gè)機(jī)器人沒有回到u結(jié)點(diǎn)的最優(yōu)解

對(duì)于每一棵子樹都是需要遍歷完的，所以必須選擇一個(gè)方案

為了保證至少選擇一個(gè)方案，所以在考慮當(dāng)前兒子v的時(shí)候先將答案加上一個(gè)狀態(tài)，這里是加上沒有機(jī)器人留在v子樹的方案

然后再對(duì)v做一個(gè)背包，若有更優(yōu)解則初始放置的選擇將被替換掉

其實(shí)相當(dāng)于對(duì)于子樹v有k件物品來選擇，必須選擇一件

13.HDU 4276

題意：每個(gè)點(diǎn)有點(diǎn)權(quán)，邊有花費(fèi)，問T時(shí)間能否從1到達(dá)n，若能，能獲取的最大權(quán)值是多少

首先想到樹中兩點(diǎn)的路徑是唯一的，既然要從1到達(dá)n，先考慮最短路徑能否到達(dá)

之后剩余的時(shí)間作為背包容量，因?yàn)槠溆嗟狞c(diǎn)都是非必須的，所以去了必須還要回來，故每條非必要的邊花費(fèi)都需要*2

?所以做法就是先把總時(shí)間減去1到n的路徑距離，并把路徑上的花費(fèi)置零

然后對(duì)于每一個(gè)結(jié)點(diǎn)做背包，對(duì)于u的兒子v枚舉一個(gè)花費(fèi)k，注意邊的花費(fèi)要double

#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #include"bitset" #define LL long long #define ull unsigned long long #define mems(a,b) memset(a,b,sizeof(a)) #define mdzz int mid=(L+R)>>1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N = 105; const int M = N<<1; const LL MOD = 998244353; const int INF = 0x3f3f3f3f;struct node{int e,next,w;node(){}node(int a,int b,int c):e(a),next(b),w(c){} }edge[N<<1];int tot; int first[N],dp[N][N*5],pre[N],id[N],w[N],inq[N],dis[N];void init(){tot=0;mems(first,-1);mems(dp,0);mems(inq,0);mems(dis,INF); }void addedge(int u,int v,int W){edge[tot]=node(v,first[u],W);first[u]=tot++;edge[tot]=node(u,first[v],W);first[v]=tot++; }int n,m,cnt; queue<int>q;void bfs(int s){while(!q.empty()) q.pop();pre[s]=1;dis[s]=0;inq[s]=1;q.push(s);while(!q.empty()){int u=q.front();q.pop();inq[u]=0;if(u==n) break;for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(!inq[v]&&dis[u]+edge[i].w<dis[v]){dis[v]=dis[u]+edge[i].w;q.push(v);inq[u]=1;pre[v]=u;id[v]=i;}}}cnt=0;int u=n;while(u!=1){cnt+=edge[id[u]].w;edge[id[u]].w=edge[id[u]^1].w=0;u=pre[u];} }void dfs2(int u,int fa){for(int i=0;i<=m;i++) dp[u][i]=w[u];for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dfs2(v,u);for(int j=m;j>=0;j--)for(int k=0;k<=j;k++) if(j-edge[i].w*2-k>=0)dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-edge[i].w*2-k]);} }int u,v,W; int main(){//freopen("in.txt","r",stdin);while(~scanf("%d%d",&n,&m)){init();for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&W);addedge(u,v,W);}for(int i=1;i<=n;i++) scanf("%d",&w[i]);bfs(1);if(cnt>m){printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");continue;}m-=cnt;dfs2(1,-1);/*for(int i=1;i<=n;i++){cout<<i<<':'<<endl;for(int j=0;j<=m;j++) cout<<dp[i][j]<<' ';cout<<endl;}*/printf("%d\n",dp[1][m]);}return 0; } View Code

14.HDU 3586

題意：給一個(gè)限制m，切斷的路徑權(quán)值和不超過m，單個(gè)邊權(quán)值也不超過k，求最小的k使得所有葉子和根不相連

二分一個(gè)k

對(duì)于一個(gè)確定的k，dp[u]表示u的葉子全部和u分離需要的最小花費(fèi)

考慮葉子節(jié)點(diǎn)：dp[u]=INF（不合法狀態(tài)

考慮非葉子結(jié)點(diǎn)：一開始是沒有和兒子相連，所以dp[u]=0

考慮u的一個(gè)兒子v，若（u,v）這條邊是<=lim，則可以選擇在消除這條邊或者是在v的子樹中消除，兩者取一個(gè)最優(yōu)解

最后判斷dp[1]是否小于給定的m

15. POJ 3107

題意：輸出樹中的結(jié)點(diǎn)k，刪去k后產(chǎn)生的最大的聯(lián)通塊最小

直接兩次dp就好了，第一次處理子樹第二次考慮父親除去當(dāng)前結(jié)點(diǎn)產(chǎn)生的最大塊，維護(hù)個(gè)最大值

16.POJ 3140

題意：選擇一條樹邊斷開，使得分成的兩部分的總點(diǎn)權(quán)差最小，輸出最小值

就直接預(yù)處理每一個(gè)點(diǎn)及其子樹的總點(diǎn)權(quán)

枚舉一個(gè)點(diǎn)和其父親斷開，取個(gè)最優(yōu)值就好了

17. POJ 2486

題意：從樹根1走K步能獲得的最大點(diǎn)權(quán)，可以走回頭路

dp[u][i][0/1]表示從u出發(fā)走i步，最終回到u/不回到u的最優(yōu)值

考慮一個(gè)葉子結(jié)點(diǎn)：dp[u][0][0]=w[u];

考慮一個(gè)非葉子結(jié)點(diǎn)u及其一個(gè)兒子v，枚舉一個(gè)k表示對(duì)于這個(gè)兒子v走的步數(shù)

有3種結(jié)果：留在v子樹，回到u，留在u其它子樹

畫圖就能看出三種情況的轉(zhuǎn)移：

留在v子樹:狀態(tài)分裂為dp[u][j-k-1][0],dp[v][k][1] ?花費(fèi)為1步

回到u:狀態(tài)分裂為dp[u][j-k-2][0],dp[v][k][0] 花費(fèi)為2步

留在其他子樹:狀態(tài)分裂為dp[u][j-k-2][1],dp[v][k][0] 花費(fèi)為2步

18. HDU 4044

題意：每個(gè)點(diǎn)有ki種選擇，每種選擇對(duì)應(yīng)一種一種花費(fèi)一種收益問擁有m元，令x為1到所有葉子（不含1）的路徑的點(diǎn)權(quán)和最小值

求x的最大值

一開始的想法是的定義dp[u][i][0/1]為u子樹花i元，u選或者不選的答案

但是后面會(huì)發(fā)現(xiàn)這樣定義狀態(tài)的話對(duì)于dp[u][i][1]的合并不是很好處理，因?yàn)槲覜]有記錄u選擇的是哪個(gè)方案

看了題解后學(xué)了一個(gè)新姿勢(shì)

定義dp[u][i]為u不選的時(shí)候花i元的最優(yōu)解

預(yù)處理一個(gè)w[u][i]表示u結(jié)點(diǎn)花i元最多能獲得的權(quán)值

考慮一個(gè)葉子結(jié)點(diǎn)：dp[u][i]=w[u][i]

考慮一個(gè)非葉子結(jié)點(diǎn)不選時(shí)候:每一個(gè)兒子v加進(jìn)來的時(shí)候，狀態(tài)都分裂為dp[v][k]和dp[u][j-k]

對(duì)于每一個(gè)枚舉的k來說，答案是min(dp[v][k],dp[u][j-k]) 維護(hù)這個(gè)答案的最大值就是dp[u][j]

考慮完u不選的情況后，再對(duì)u單獨(dú)做一次背包，枚舉u的花費(fèi)，取個(gè)最優(yōu)值就是答案

?19.HDU 5758

題意：點(diǎn)有點(diǎn)權(quán)邊有花費(fèi)，點(diǎn)權(quán)只能獲得一次，花費(fèi)每次經(jīng)過都要扣除，可以走回頭路，問能拿到的最大價(jià)值

參考Apple Tree可以知道需要加一維[0/1]表示是否回到u

定義dp[u][0/1]表示從u出發(fā)不回/回到u的最優(yōu)解

求一個(gè)結(jié)點(diǎn)對(duì)于整棵樹的信息一般都是先處理子樹內(nèi)的信息，再第二次dfs處理父親對(duì)答案的影響

先考慮子樹內(nèi)：

考慮一個(gè)葉子結(jié)點(diǎn)：dp[u][0]=dp[u][1]=w[u]

考慮一個(gè)非葉子u和他的一個(gè)兒子v：

對(duì)于dp[u][0]來說，v的貢獻(xiàn)只能是dp[v][0]-2*w[u,v]，如果這個(gè)值小于0我必然不走v

對(duì)于dp[u][1]來說，如果不停在v內(nèi)，v的貢獻(xiàn)也是dp[v][0]-2*w[u,v]，如果停在u則狀態(tài)分裂為dp[u][0]+dp[v][1]-w[u,v]

再考慮fa對(duì)u的影響

考慮fa對(duì)u的影響時(shí)一般需要把u對(duì)fa的影響先排除

對(duì)于dp[fa][0]來說u的影響只能是max(0,dp[u][0]-2*w[fa,u])，直接減去就行了

對(duì)于dp[fa][1]來說有兩種情況

若最終不停在u，則和dp[fa][0]一樣處理

若停在u，則需要對(duì)fa再做一次排除u后的背包

這里將fa對(duì)u的影響作為參數(shù)下傳，為的是保證在推u的時(shí)候fa的值是對(duì)于整棵樹的，而其余結(jié)點(diǎn)是對(duì)于其子樹的

之所以這樣做是因?yàn)橛胒a更新u的時(shí)候，排除u對(duì)fa的影響之后fa相當(dāng)于u的一棵新子樹

#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #include"bitset" #define LL long long #define ull unsigned long long #define mems(a,b) memset(a,b,sizeof(a)) #define mdzz int mid=(L+R)>>1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N = 1e5+50; const int M = N<<1; const LL MOD = 998244353; const int INF = 0x3f3f3f3f;struct node{int e,next,w;node(){}node(int a,int b,int c):e(a),next(b),w(c){} }edge[N<<1];int tot,n,m; int first[N],dp[N][2],w[N],id[N];void init(){tot=0;for(int i=1;i<=n;i++) first[i]=-1; }void addedge(int u,int v,int W){edge[tot]=node(v,first[u],W);first[u]=tot++;edge[tot]=node(u,first[v],W);first[v]=tot++; }void dfs1(int u,int fa){dp[u][0]=dp[u][1]=w[u];id[u]=-1;for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dfs1(v,u);int tmp=max(0,dp[v][0]-2*edge[i].w);dp[u][1]+=tmp;if(dp[u][1]<dp[u][0]+max(0,dp[v][1]-edge[i].w)){dp[u][1]=dp[u][0]+max(0,dp[v][1]-edge[i].w);id[u]=v;}dp[u][0]+=tmp;} } int ans[N]; void dfs2(int u,int fa,int f0,int f1){int t[2]={dp[u][0],dp[u][1]};int idd=id[u];t[1]+=f0;if(t[1]<t[0]+f1){t[1]=t[0]+f1;idd=fa;}t[0]+=f0;ans[u]=max(t[0],t[1]);for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;if(v==idd){int tmp0=w[u]+f0,tmp1=w[u]+f1;for(int k=first[u];k!=-1;k=edge[k].next){int vv=edge[k].e;if(vv==fa||vv==v) continue;int tmp=max(0,dp[vv][0]-2*edge[k].w);tmp1+=tmp;tmp1=max(tmp1,tmp0+max(0,dp[vv][1]-edge[k].w));tmp0+=tmp;}tmp0=max(0,tmp0-2*edge[i].w);tmp1=max(0,tmp1-edge[i].w);dfs2(v,u,tmp0,tmp1);}else{int tmp=max(0,dp[v][0]-2*edge[i].w);int tmp0=max(0,t[0]-tmp-2*edge[i].w);int tmp1=max(0,t[1]-tmp-edge[i].w);dfs2(v,u,tmp0,tmp1);}} }int T,u,v,W,cas=1;int main(){//freopen("in.txt","r",stdin);//freopen("pending.txt","w",stdout);scanf("%d",&T);while(T--){scanf("%d",&n);init();for(int i=1;i<=n;i++) scanf("%d",&w[i]);for(int i=1;i<n;i++){scanf("%d%d%d",&u,&v,&W);addedge(u,v,W);}dfs1(1,-1);dfs2(1,-1,0,0);printf("Case #%d:\n",cas++);for(int i=1;i<=n;i++) printf("%d\n",ans[i]);}return 0; } View Code

?20.NUBT 1638

題意：建圖略麻煩，抽象出來就是說樹中選m個(gè)結(jié)點(diǎn)，其中rt到每一個(gè)葉子的路徑上被選的結(jié)點(diǎn)數(shù)不超過k，問獲得的最大權(quán)值是多少

定義dp[u][i][j][0/1]表示u子樹選i個(gè)，最多的路徑選了j個(gè)，u選/不選

dp值全部初始化為-1表示不合法狀態(tài)

考慮一個(gè)葉子結(jié)點(diǎn):選的話是dp[u][1][1][1]=w[u] ?不選dp[u][0][0][0]=0

考慮一個(gè)非葉子結(jié)點(diǎn)u和他的一個(gè)兒子v：

對(duì)于狀態(tài)dp[u][i][j][0]，可能轉(zhuǎn)移過來的狀態(tài)有dp[u][i-k][j][0]+dp[v][k][0~j][0/1]或者dp[u][i-k][0~j][0]+dp[v][k][j][0/1]

對(duì)于狀態(tài)dp[u][i][j][1]，有dp[u][i-k][j][1]+dp[v][k][0~j-1][0/1]或dp[u][i-k][0~j][1]+dp[v][k][j-1][0/1](之所以v是j-1為上限是因?yàn)閡選了的話合并后v的最長鏈長度必然+1，這樣做是為了限制最長鏈在j范圍內(nèi))

#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #include"bitset" #define LL long long #define ull unsigned long long #define mems(a,b) memset(a,b,sizeof(a)) #define mdzz int mid=(L+R)>>1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N = 120; const int M = N<<1; const LL MOD = 998244353; const int INF = 0x3f3f3f3f;struct Point{int x,y; }p[N<<2];bool cmp(Point a,Point b){return a.x<b.x; }struct Node{int y,l,r; }point[N];bool cmp1(Node a,Node b){if(a.y==b.y) return a.l<b.l;return a.y>b.y; }struct node{int e,next; }edge[N<<1];int first[N],cnt,tot; int dp[N][N][11][2],w[N],sz[N];void init(){tot=0;cnt=0;mems(first,-1);mems(dp,-1); }void addedge(int u,int v){edge[tot]=(node){v,first[u]};first[u]=tot++; }void build(int l,int r,int fa){for(int i=l+1;i<=r;i++){if(p[l].y==p[i].y){addedge(fa,++cnt);w[cnt]=p[i].x-p[l].x;//cout<<fa<<' '<<cnt<<' '<<w[cnt]<<endl;build(l+1,i-1,cnt);build(i,r,fa);return ;}else if(p[i].y>p[l].y){build(l+1,i-1,fa);build(i,r,fa);}} }int n,m,K;void dfs(int u){dp[u][1][1][1]=w[u];dp[u][0][0][0]=0;sz[u]=1;for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;dfs(v);sz[u]+=sz[v];for(int j=sz[u];j>=0;j--)for(int k=0;k<=K;k++)for(int p=0;p<=min(sz[v],j);p++)for(int kk=0;kk<=k;kk++){if(dp[u][j-p][k][0]!=-1&&(dp[v][p][kk][0]!=-1||dp[v][p][kk][1]!=-1))dp[u][j][k][0]=max(dp[u][j][k][0],dp[u][j-p][k][0]+max(dp[v][p][kk][0],dp[v][p][kk][1]));if(dp[u][j-p][kk][0]!=-1&&(dp[v][p][k][0]!=-1||dp[v][p][k][1]!=-1))dp[u][j][k][0]=max(dp[u][j][k][0],dp[u][j-p][kk][0]+max(dp[v][p][k][0],dp[v][p][k][1]));if(kk>=1&&dp[u][j-p][k][1]!=-1&&(dp[v][p][kk-1][0]!=-1||dp[v][p][kk-1][1]!=-1))dp[u][j][k][1]=max(dp[u][j][k][1],dp[u][j-p][k][1]+max(dp[v][p][kk-1][0],dp[v][p][kk-1][1]));if(k>=1&&dp[u][j-p][kk][1]!=-1&&(dp[v][p][k-1][0]!=-1||dp[v][p][k-1][1]!=-1))dp[u][j][k][1]=max(dp[u][j][k][1],dp[u][j-p][kk][1]+max(dp[v][p][k-1][0],dp[v][p][k-1][1]));}} }int cas=1;int main(){//freopen("in.txt","r",stdin);while(~scanf("%d%d%d",&n,&m,&K)){init();for(int i=1;i<=n;i++) scanf("%d%d",&p[i].x,&p[i].y);sort(p+1,p+1+n,cmp);build(1,n,0);int rt=0;dfs(rt);int ans=-1;for(int i=0;i<K;i++) ans=max(ans,dp[rt][m][i][0]);printf("Case %d: %d\n",cas++,ans);}return 0; } View Code

21.HDU 5758

題意：邊花費(fèi)1，可以從一個(gè)點(diǎn)瞬移到另一個(gè)點(diǎn)，問瞬移次數(shù)最少的前提下遍歷所有邊的最小花費(fèi)

可以知道瞬移次數(shù)是(葉子數(shù)+1）/2

定義dp[u][0]為遍歷完u后的最小花費(fèi)(只是第一次dp，答案不一定是最終答案

考慮非葉子u和他的一個(gè)兒子v:

若v有偶數(shù)個(gè)兒子，則要在瞬移次數(shù)最少的情況下遍歷(u,v)這條邊，就必須有兩個(gè)結(jié)點(diǎn)和v外的結(jié)點(diǎn)配對(duì)，所以(u,v)對(duì)答案貢獻(xiàn)2

同理奇數(shù)的時(shí)候貢獻(xiàn)1

如果總?cè)~子數(shù)是偶數(shù)那答案已經(jīng)出來了

但是如果總?cè)~子數(shù)是奇數(shù)這樣的答案可能會(huì) 偏大

其實(shí)奇數(shù)的情況就是在偶數(shù)的情況加了一條沒有分叉的單鏈

所以再定義dp[u][1]為遍歷u后的最小花費(fèi)(第二次dp，獨(dú)立與第一次dp

對(duì)于一個(gè)u，枚舉這條單鏈出現(xiàn)的兒子v：

如果這個(gè)兒子就是一條單鏈，并且u是這條單鏈的起點(diǎn)，則dp[u][1]=min(dp[u][1],dp[u][0])

如果不是兒子v不是單鏈則把這條單鏈從v中剔除，則v中的葉子數(shù)的奇偶就變化了

dp[u][1]先減去dp[v][0]，再減去奇偶變化的影響d，再加上單鏈存在與v的dp值dp[v][1]，維護(hù)最優(yōu)解

最后若總?cè)~子數(shù)是偶數(shù)則取第一次dp的結(jié)果，否則取第二次的

?22.codeforces Round #322(Div.2) F

題意：把葉子平分染成兩種顏色，其余點(diǎn)隨便染，求最少有對(duì)相鄰的點(diǎn)顏色不同 ?輸入保證葉子是偶數(shù)個(gè)

定義dp[u][i][0/1]表示u子樹染i個(gè)兒子0色，u染0/1色

這題經(jīng)典的地方在于葉子和非葉子的初始情況不一樣

先dp值全部賦INF表示不合法

對(duì)于葉子來說：dp[u][1][0]=0,dp[u][0][1]=0，其余兩個(gè)狀態(tài)不合法

考慮非葉子u：

非葉子u的顏色對(duì)第二維是沒影響的,所以dp[u][0][1]=dp[u][0][0]=0

由于這里是必須要選擇兒子的情況，之前有些題目是兒子可以不選

必須選的情況的處理方法有兩種，第一種是先強(qiáng)制放一種狀態(tài)，再枚舉其他狀態(tài)看看是否更優(yōu)，有就替換，沒有就保留原來的

或者說是用一個(gè)變量去存放兒子的最優(yōu)情況，然后把這個(gè)最優(yōu)情況強(qiáng)制合并到原狀態(tài)里

這里我采用的是第二種方法

23.COJ 1793

題意：對(duì)于每個(gè)點(diǎn)給一個(gè)限制xi表示xi選了才能選i，現(xiàn)在最多選m個(gè)人，問在這些限制下最多能選幾個(gè)

如果連邊(xi->i)一眼看過去結(jié)構(gòu)很像樹，因?yàn)槊總€(gè)結(jié)點(diǎn)只有一個(gè)父親

但是這里可能會(huì)構(gòu)成強(qiáng)聯(lián)通分量

不過很容易想到把強(qiáng)聯(lián)通分量縮點(diǎn)后也是可以構(gòu)成樹或者森林的

森林我們可以建立一個(gè)虛根0來合并成一棵樹

一開始有個(gè)地方?jīng)]想明白，就是對(duì)于一個(gè)強(qiáng)聯(lián)通分量來說可能去掉一個(gè)點(diǎn)后還是強(qiáng)聯(lián)通分量，所以一個(gè)強(qiáng)聯(lián)通分量內(nèi)我選擇幾個(gè)人是不好判斷的

但是仔細(xì)想想題目給的條件，每個(gè)點(diǎn)的入度只能為1，而這樣構(gòu)成的強(qiáng)聯(lián)通分量只能是一個(gè)簡單環(huán)

而對(duì)于一個(gè)簡單環(huán)來說我只能全取或者全不取

所以問題就轉(zhuǎn)化為了一個(gè)m的背包，每個(gè)點(diǎn)的sz即使花費(fèi)也是價(jià)值，問能拿到的最大價(jià)值是多少

這里有個(gè)地方需要變通

這里是選了父親才能選擇兒子，所以對(duì)于一個(gè)結(jié)點(diǎn)u以及他的兒子v來說，我要把v加進(jìn)來我首先得保證u被選

所以我枚舉v的容量k的時(shí)候始終保證j-k也就是剩余的容量始終是大于sz[u]的，這樣就能保證u始終被選

#include"cstdio" #include"queue" #include"cmath" #include"stack" #include"iostream" #include"algorithm" #include"cstring" #include"queue" #include"map" #include"set" #include"vector" #include"bitset" #define LL long long #define ull unsigned long long #define mems(a,b) memset(a,b,sizeof(a)) #define mdzz int mid=(L+R)>>1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std;const int N = 1e3+5; const int M = N<<1; const LL MOD = 998244353; const int INF = 0x3f3f3f3f;struct node{int s,e,next; }edge[M];int tot,id; int first[N]; int block,tp,n,m; int low[N],dfn[N],ins[N],deg[N]; int st[N],belong[N],sz[N]; int dp[N][N];void init(int n){tot=0;tp=0;block=0;id=0;for(int i=0;i<=n;i++){first[i]=-1;dfn[i]=0;ins[i]=0;deg[i]=0;for(int j=0;j<=m;j++) dp[i][j]=0;} }void addedge(int u,int v){edge[tot]=(node){u,v,first[u]};first[u]=tot++;//edge[tot]=(node){u,first[v]};//first[v]=tot++; }void tarjan(int u){low[u]=dfn[u]=++id;ins[u]=1;st[++tp]=u;for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(!dfn[v]){tarjan(v);low[u]=min(low[u],low[v]);}else if(ins[v]) low[u]=min(low[u],dfn[v]);}if(low[u]==dfn[u]){block++;sz[block]=0;int v;do{v=st[tp--];ins[v]=0;belong[v]=block;sz[block]++;}while(v!=u);} }void rebuild(){int tot2=tot;tot=0;for(int i=0;i<=n;i++) first[i]=-1;for(int i=0;i<tot2;i++){int u=belong[edge[i].s];int v=belong[edge[i].e];if(u==v) continue;deg[v]++;addedge(u,v);} }void dfs(int u,int fa){for(int i=sz[u];i<=m;i++) dp[u][i]=sz[u];for(int i=first[u];i!=-1;i=edge[i].next){int v=edge[i].e;if(v==fa) continue;dfs(v,u);for(int j=m;j>=sz[u];j--)for(int k=0;k<=j-sz[u];k++)dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);} } int u;int main(){//freopen("in.txt","r",stdin);while(~scanf("%d%d",&n,&m)){init(n);for(int i=1;i<=n;i++){scanf("%d",&u);addedge(u,i);}for(int i=1;i<=n;i++) if(!dfn[i]) tarjan(i);rebuild();int rt=0;sz[0]=0;for(int i=1;i<=block;i++) if(!deg[i]) addedge(rt,i);dfs(rt,-1);printf("%d\n",dp[rt][m]==-1?0:dp[rt][m]);}return 0; } View Code

轉(zhuǎn)載于:https://www.cnblogs.com/luxiaoming/p/5824297.html

總結(jié)

以上是生活随笔為你收集整理的树形DP 学习总结的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。

上一篇：封装javascript分页插件——可以
下一篇： Swift-数组