樹形DP刷題小記
- 最大子樹和
- 選課
- 積蓄程度
- 二叉蘋果樹
最大子樹和
鏈接:P1122 最大子樹和
演算法分析
典型的樹形DP，要結合貪心的思想，f[x]存盤以x為根可以得到的最大美麗值,若子樹的美麗值小于零，即對結果有害，應減去，
狀態轉移方程:
f
[
x
]
+
=
f
[
y
]
>
0
?
f
[
y
]
:
0
f[x]+=f[y]>0?f[y]:0
f[x]+=f[y]>0?f[y]:0
Code：
#include<bits/stdc++.h>
using namespace std;
inline int Read(){
int dx=0,fh=1;
char c;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
dx=dx*10+c-'0';
c=getchar();
}
return dx*fh;
}
struct node{
int to,next;
}edg[170000];
int n,beauty[170000],h[170000],cnt,ans,f[170000];
void add(int a,int b){
++cnt;
edg[cnt].to=b;
edg[cnt].next=h[a];
h[a]=cnt;
}
void dfs(int u){
f[u]=beauty[u];
for(int i=h[u];i;i=edg[i].next){
int v=edg[i].to;
dfs(v);
if(f[v]>0) f[u]+=f[v];
}
ans=max(ans,f[u]);
}
int main(){
n=Read();
for(int i=1;i<=n;++i) beauty[i]=Read();
for(int i=1;i<=n-1;++i){
int aa,bb;
aa=Read(),bb=Read();
add(aa,bb);add(bb,aa);
}
dfs(1);
printf("%d",ans);
return 0;
}
總結與反思
- 結合不同演算法的思想對于代碼很有幫助
- 陣列開大(最好題中資料的2倍)
選課
鏈接:P2014 [CTSC1997]選課
演算法分析:
樹形分類背包DP，每個先修課都是后驅課的父節點，整個圖即為一個森林，每個根節點可以連接到一個虛擬的價值為0的總先驅節點，由于先驅節點占空間，背包容量要加一，設
f
[
x
]
[
y
]
f[x][y]
f[x][y]為以
x
x
x為根，占用
y
y
y個空間的最大學分,然后利用多重背包來解即可，
Code:
#include<bits/stdc++.h>
using namespace std;
inline int Read(){
int dx=0,fh=1;
char c;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
dx=dx*10+c-'0';
c=getchar();
}
return dx*fh;
}
struct node{
int to,next;
}edg[17000];
int n,m,h[1700],score[1000],cnt,ans,f[17000][500];
void add(int a,int b){
++cnt;
edg[cnt].to=b;
edg[cnt].next=h[a];
h[a]=cnt;
}
void dfs(int u){
f[u][1]=score[u];
int flag=1;
for(int i=h[u];i;i=edg[i].next){
flag=0;
int v=edg[i].to;
dfs(v);
for(int j=m;j>=1;--j)
for(int k=1;k<j;++k)
f[u][j]=max(f[u][j],f[v][k]+f[u][j-k]);
}
if(flag==1)
for(int i=2;i<=m+1;++i)
f[u][i]=f[u][i-1];
}
int main(){
n=Read(),m=Read();
for(int i=1;i<=n;++i){
int pre;
pre=Read();
score[i]=Read();
add(pre,i);
}
++m;
dfs(0);
printf("%d",f[0][m]);
return 0;
}
總結與反思
- 要通過虛擬根把森林轉化成一棵樹
- 要注意處理虛擬根帶來的占用背包空間的影響（背包空間應加一）
- 背包要通過逆序回圈來節省維度
積蓄程度
鏈接:287. 積蓄程度
演算法分析:
該數是一個無根樹，可以以任意一點為根，因此一個最樸素的思想就是以單個節點為根，打一遍DP，
但是…時間復雜度感人，因此，要找一種更為巧妙的方式，
設
c
[
i
]
[
j
]
c[i][j]
c[i][j]為
i
i
i與
j
j
j之間的容量，先以任意一點（設為root）為根，用
d
[
x
]
d[x]
d[x]存盤
x
x
x節點對于它的子樹的最大流量，易得狀態轉移方程:
d
[
x
]
=
Σ
m
i
n
(
d
[
y
]
+
c
[
x
]
[
y
]
)
d[x]=\Sigma min(d[y]+c[x][y])
d[x]=Σmin(d[y]+c[x][y])
一遍dfs就能把所有的
d
d
d求出來了，然后設
f
[
x
]
f[x]
f[x]為以
x
x
x為源的整個樹的流量，顯然，
f
[
r
o
o
t
]
=
d
[
r
o
o
t
]
f[root]=d[root]
f[root]=d[root]，
由于知道的是根，因此要從上往下遞推,若已知
f
[
u
]
f[u]
f[u]，則
f
[
v
]
f[v]
f[v]可分為兩部分，
f
[
v
]
f[v]
f[v]的子樹(
d
[
v
]
d[v]
d[v])以及整棵樹除了
v
v
v的子樹以外的部分，
先看特殊情況：
u
u
u點的度為1,則以
u
u
u為根時，水流全部入
v
v
v點，易得狀態轉移方程:
f
[
v
]
=
d
[
v
]
+
c
[
i
]
[
j
]
f[v]=d[v]+c[i][j]
f[v]=d[v]+c[i][j]
我們知道以
u
u
u為根時，
u
u
u->
v
v
v的流量
=
m
i
n
(
d
[
v
]
,
c
[
u
]
[
v
]
)
=min(d[v],c[u][v])
=min(d[v],c[u][v])，所以
u
u
u流向其他地方的流量為
f
[
v
]
?
m
i
n
(
d
[
v
]
,
c
[
u
]
[
v
]
)
f[v]-min(d[v],c[u][v])
f[v]?min(d[v],c[u][v]),即為以
v
v
v根時，
u
u
u子樹的最大承載度:
不難得出狀態轉移方程:
f
[
v
]
=
d
[
v
]
+
m
i
n
(
f
[
v
]
?
m
i
n
[
d
[
v
]
,
c
[
u
]
[
v
]
,
c
[
u
]
[
v
]
)
f[v]=d[v]+min(f[v]-min[d[v],c[u][v],c[u][v])
f[v]=d[v]+min(f[v]?min[d[v],c[u][v],c[u][v])
然后碼就完了，
Code:
#include<bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
const int INF=2147483647;
inline int Read(){
int dx=0,fh=1;
char c;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
dx=dx*10+c-'0';
c=getchar();
}
return dx*fh;
}
struct node{
int to,next,val;
}edg[300000];
int n,h[300000],cnt,ans,f[300000],T,d[300000],dgr[300000];
void add(int a,int b,int val){
++cnt;
edg[cnt].to=b;
edg[cnt].next=h[a];
edg[cnt].val=val;
h[a]=cnt;
}
void dfs1(int fa,int u){
if(dgr[u]==1&&fa==edg[h[u]].to) d[u]=INF;
for(int i=h[u];i;i=edg[i].next){
int v=edg[i].to;
if(v==fa) continue;
dfs1(u,v);
d[u]+=min(d[v],edg[i].val);
}
}
void dfs(int fa,int u){
for(int i=h[u];i;i=edg[i].next){
int v=edg[i].to;
if(v==fa) continue;
if(dgr[u]==1) f[v]=edg[i].val;
else f[v]=min(edg[i].val,f[u]-min(edg[i].val,d[v]));
if(dgr[v]>1) f[v]+=d[v];
dfs(u,v);
}
ans=max(ans,f[u]);
}
void Init(){
memset(edg,0,sizeof(edg));
memset(h,0,sizeof(h));
memset(f,0,sizeof(f));
memset(d,0,sizeof(d));
memset(dgr,0,sizeof(dgr));
n=0;cnt=0;ans=0;
}
int main(){
T=Read();
for(int TT=1;TT<=T;++TT){
Init();
n=Read();
for(int i=1;i<n;++i){
int aa,bb,cc;
aa=Read();bb=Read();cc=Read();
++dgr[aa];++dgr[bb];
add(aa,bb,cc);
add(bb,aa,cc);
}
dfs1(0,1);
f[1]=d[1];
dfs(0,1);
printf("%d\n",ans);
}
return 0;
}
總結與反思:
- 要注意特殊情況的處理方式
- 要從資料范圍來大致推算出時間復雜度限制，來選擇合適的演算法
- 多組資料要在每算完一個答案后初始化
二叉蘋果樹
鏈接:P2015 二叉蘋果樹
演算法分析：
先把整棵樹的基本資訊弄明白，遍歷一遍，求出每個節點的左子樹
l
[
]
l[]
l[]與右子樹
r
[
]
r[]
r[]，題目中說保留
m
m
m條邊，相當于保留
m
+
1
m+1
m+1個節點，每個邊上的蘋果可以轉移到該邊連接的兒子上面，然后設
f
[
u
]
[
i
]
f[u][i]
f[u][i]為以
u
u
u為根的子樹占用
i
i
i個節點可獲得的最大蘋果樹，
目標：
f
[
1
]
[
m
+
1
]
f[1][m+1]
f[1][m+1]
邊界條件:
- f [ l e a v e s ] [ i ] = a p p l e [ l e a v e s ] ( 0 < i < m + 1 ) f[leaves][i]=apple[leaves](0<i<m+1) f[leaves][i]=apple[leaves](0<i<m+1)
- f [ u ] [ 1 ] = a p p l e [ u ] f[u][1]=apple[u] f[u][1]=apple[u]
可推出狀態轉移方程:
f
[
u
]
[
i
]
=
m
a
x
(
f
[
l
[
u
]
]
[
k
]
+
f
[
r
[
u
]
]
[
j
?
k
?
1
]
+
a
p
[
u
]
)
f[u][i]=max(f[l[u]][k]+f[r[u]][j-k-1]+ap[u])
f[u][i]=max(f[l[u]][k]+f[r[u]][j?k?1]+ap[u])
Code:
#include<bits/stdc++.h>
using namespace std;
inline int Read(){
int dx=0,fh=1;
char c;
c=getchar();
while(c<'0'||c>'9'){
if(c=='-') fh=-1;
c=getchar();
}
while(c<='9'&&c>='0'){
dx=dx*10+c-'0';
c=getchar();
}
return dx*fh;
}
struct node{
int to,next,val;
}edg[3000];
int n,h[3000],cnt,ans,f[1000][1006],m,l[1006],r[1006],ctt[1006],ap[1006];
void add(int a,int b,int val){
++cnt;
edg[cnt].to=b;
edg[cnt].next=h[a];
edg[cnt].val=val;
h[a]=cnt;
}
void dfs1(int u,int fa){
int flag=0;
for(int i=h[u];i;i=edg[i].next){
int v=edg[i].to;
if(v==fa) continue;
ap[v]=edg[i].val;
flag=1;
if(ctt[u]==0) l[u]=v,++ctt[u];
else r[u]=v;
dfs1(v,u);
}
if(flag==0)
for(int i=1;i<=m;++i)
f[u][i]=edg[h[u]].val;
f[u][1]=ap[u];
}
void dfs(int u,int fa){
for(int i=h[u];i;i=edg[i].next){
int v=edg[i].to;
if(v==fa) continue;
dfs(v,u);
for(int j=2;j<=m;++j)
for(int k=0;k<j;++k)
f[u][j]=max(f[u][j],f[l[u]][k]+f[r[u]][j-k-1]+ap[u]);
}
}
int main(){
n=Read(),m=Read();++m;
for(int i=2;i<=n;++i){
int aa=Read(),bb=Read(),cc=Read();
add(aa,bb,cc);
add(bb,aa,cc);
}
dfs1(1,0);
dfs(1,0);
printf("%d",f[1][m]);
return 0;
}
總結與反思:
- 每個子樹的根一定要算在 f f f內
- 要學會用更加簡單的方法存二叉樹
- 邊帶權要學會轉化為點帶權，同時剩余的邊數轉化為剩余的點數時要加一
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/243618.html
標籤：其他
上一篇：2020，開啟我人生的新篇章。