前言 今日偶然打開 $oi-wiki$，發現樹形 $DP$ 例題正好是之前在洛谷上鴿著的一道題。所以...... $\color{red}{很高興以這樣的方式認識你，樹形 DP !}$ 這例題造的太好了，簡直是無痛入門（感動.jpg） P1352 沒有上司的舞會 題目傳送門~ 思路剖析 狀態定義 $ ...
前言
今日偶然打開 \(oi-wiki\)，發現樹形 \(DP\) 例題正好是之前在洛谷上鴿著的一道題。所以......
\(\color{red}{很高興以這樣的方式認識你，樹形 DP !}\)
這例題造的太好了，簡直是無痛入門（感動.jpg）
P1352 沒有上司的舞會
思路剖析
狀態定義
\(dp_i\) 表示的是以 \(i\) 為根節點的子樹所獲得的最大價值。
由於每個節點代表著一位人物，有來與不來兩種狀態，所以再加一維狀態變數。
\(dp_{i,0}\) 表示以 \(i\) 為根節點的子樹所能獲得的最大價值，且這位人物沒來。 \(dp_{i,1}\) 則對應來了的狀態。
狀態轉移方程
現在有個周年慶宴會，宴會每邀請來一個職員都會增加一定的快樂指數 r_i。
但是呢，如果某個職員的直接上司來參加舞會了，那麼這個職員就無論如何也不肯來參加舞會了。
根據題意描述，容易得出狀態轉移方程：
\(dp_{i,0} += max (dp_{j,0},dp_{j,1})\)
\(dp_{i,1} += dp_{j,0}\)
\(j\) 指的是 \(i\) 的子節點，且顯然 \(dp_{i,1}\) 的初始值為 \(r_i\)。
code
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[6005];
int head[6005],nex[6005],edge[6005],tot;
int vis[6005],dp[6005][2];
void dfs(int x){
dp[x][1]=a[x];
for(int i=head[x];i;i=nex[i]){
int y=edge[i];
dfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
}
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++){
int l,k;
scanf("%d%d",&l,&k);
nex[++tot]=head[k];
head[k]=tot;
edge[tot]=l;
vis[l]=1;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
cout<<max(dp[i][0],dp[i][1])<<endl;
return 0;
}
}
}
P1122 最大子樹和
思路剖析
誰是根節點
由於這題是無向圖（但由於以 \(n-1\) 條邊相連接，所以本質與樹並無太大區別），所以要討論以誰作為根節點。
根節點之所以重要，是因為在遞歸過程中，我們已經預設根節點所代表的那束花已經被保留了，但根節點代表的花不一定在最優解的集合之中。
仔細模擬後，不難發現，對於以 \(i\) 為根節點的子樹，\(dp_i\) 往下為最優解，而往上由於還未更新，因此相當於剪去 \(dp_i\) 與其根節點的枝椏。
進一步推理，無論通過哪個節點作為根節點，再遞歸的過程中，其實已經變相枚舉了將其剪去的種種情況，所以，只需要在過程中取最優解即可。
狀態定義+狀態轉移方程
這點比較好理解，所以合併在一起闡述。
\(dp_i\) 表示以 \(i\) 為根節點的子樹所獲得的最大美麗值。
顯然有
\(dp_i+=max(dp_j,0)\)。
\(j\) 為子節點，當其所帶來的價值為負數時，不如直接剪掉。
code
有幾處雷點在註釋中標記出來了（都是血淚教訓啊QAQ）
點擊查看代碼
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans=-0x3f3f3f3f;//答案可能為負！要初始化為負無窮
int head[16005],nex[35005],edge[35005],tot;//由於是雙向邊，所以空間要開雙倍
int dp[16005],vis[16005];
void dfs(int x){
vis[x]=1;//不要在迴圈內標記，否則標記不到根節點本身。
for(int i=head[x];i;i=nex[i]){
int y=edge[i];
if(vis[y]) continue;
dfs(y);
if(dp[y]<=0) continue;
dp[x]+=dp[y];
}
ans=max(ans,dp[x]);
return;
}
void add(int l,int k) {nex[++tot]=head[k],head[k]=tot,edge[tot]=l;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&dp[i]);
for(int i=1;i<n;i++){
int l,k;
scanf("%d%d",&l,&k);
add(l,k);
add(k,l);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
第 \(7、8\) 道，(‾◡◝)。
加油！
