消防局的建立
本題地址： http://www.luogu.org/problem/show?pid=2279

題目描述

2020年，人類在火星上建立了一個龐大的基地群，總共有n個基地。起初為了節約材料，人類只修建了n-1條道路來連接這些基地，并且每兩個基地都能夠通過道路到達，所以所有的基地形成了一個巨大的樹狀結構。如果基地A到基地B至少要經過d條道路的話，我們稱基地A到基地B的距離為d。
由于火星上非常干燥，經常引發火災，人類決定在火星上修建若干個消防局。消防局只能修建在基地里，每個消防局有能力撲滅與它距離不超過2的基地的火災。
你的任務是計算至少要修建多少個消防局才能夠確保火星上所有的基地在發生火災時，消防隊有能力及時撲滅火災。

輸入輸出格式

輸入格式：
輸入文件名為input.txt。
輸入文件的第一行為n （n<=1000），表示火星上基地的數目。接下來的n-1行每行有一個正整數，其中文件第i行的正整數為a[i]，表示從編號為i的基地到編號為a[i]的基地之間有一條道路，為了更加簡潔的描述樹狀結構的基地群，有a[i]< i。

輸出格式：
輸出文件名為output.txt
輸出文件僅有一個正整數，表示至少要設立多少個消防局才有能力及時撲滅任何基地發生的火災。

輸入輸出樣例
輸入樣例#1：
6
1
2
3
4
5
輸出樣例#1：
2

題解

這是一道蛋疼的樹形DP，樹形DP一般狀態表示比較復雜；在題解幫助下過掉；
%大神Crazyxx http://202.101.104.45:8888/space/show?uid=6076
狀態：
dp[i][0]:選自己
dp[i][1]:選了至少一個兒子
dp[i][2]:選了至少一個孫子
———————————–這三種是覆蓋了自己的
dp[i][3]: 兒子孫子全部覆蓋
dp[i][4]:孫子全部覆蓋
———————————–這兩種并沒有覆蓋自己
建議畫一棵深度為3的完全二叉樹直觀觀察狀態 否則轉移方程比較難懂

初始轉移方程：
dp[i][0] = 1+Σmin(dp[j][0…4]);
要使選了根節點之后合法（整棵子樹包括根節點被覆蓋）必須使兒子的孫子全部覆蓋 0~4狀態滿足
dp[i][1] = min( dp[k][0] + Σ(j != k)min(dp[j][0…3]) );
要使選了一個兒子之后合法 由于兒子只可以覆蓋到兄弟 所以孫子一定要全部被覆蓋 即兒子的兒子一定覆蓋 0~3滿足
dp[i][2] = min( dp[k][1] + Σ(j != k)min(dp[j][0…2]) );
使選了一個孫子之后合法 由于孫子最多只能覆蓋到當前節點 所以兒子一定全部覆蓋 即所有兒子本身要被覆蓋 0~2滿足
dp[i][3] = Σdp[j][0…2];
要使兒子及孫子全部被覆蓋 即兒子本身要被覆蓋 0~2滿足
dp[i][4] = Σdp[j][0…3];
要使孫子全部被覆蓋 即兒子的兒子要全部被覆蓋 0~3滿足
：：注意每種狀態由兒子轉移過來所以根的情況 要轉化成對于兒子來說的情況

然后改進狀態 因為每種轉移方程至少有三種可能最后取其中較小的 故時間效率較低 令dp[i][k]表示min(dp[i][0],dp[i][1]….dp[i][k])且k>=2 因為上述轉移方程最少都是0~2狀態
那么轉移方程就大幅度化簡了：
dp[i][0] = 1+Σdp[j][4];
直接由上面變形而來
dp[i][1] = dp[i][4] + min(dp[k][0]-dp[k][3]);
選一個兒子 需保證所有孫子被覆蓋 即 dp[i][4] 然后要選出一個兒子 將他從0~3狀態變為選了自己（由于dp[i][4]中他是3狀態所以要減去一個dp[k][3]） 取這個差值最小的兒子
dp[i][2] = dp[i][3] + min(dp[k][1]-dp[k][2]);
選一個孫子 與上面類似 要保證所有兒子都被覆蓋 即dp[i][3] 再將一個兒子從0~2狀態變為0~1狀態以保證覆蓋他父節點
dp[i][3] = Σdp[j][2];
保證所有兒子被覆蓋 兒子的0~2狀態均符合條件
dp[i][4] = Σdp[j][3];
保證所有兒子的兒子被覆蓋 兒子的0~3狀態均符合條件

別問我為什么dp[i][1]和dp[1][2]用到后面的狀態 因為你只需要在過程中記下那一坨min的值 把3,4處理完后再算1,2
另外由于數據特殊性 編號大的節點一定是編號小的節點的后代 所以遞推順序直接到著推就好了

---

代碼：（神犇的代碼稍作改動）

#include<iostream> #include<algorithm> #include<cstdio> using namespace std; const int maxn=1000+10; const int INF=(1<<30);bool G[maxn][maxn]; int dp[maxn][5]; int main() {int n;cin>>n;for(int i=2,tmp;i<=n;i++){scanf("%d",&tmp);G[tmp][i]=1;}for(int i = n ; i>=1 ; i--){int x1=INF,x2=INF;dp[ i ][ 0 ]=1;for(int j=1;j<=n;j++)if(G[ i ][ j ]){dp[ i ][ 0 ]+=dp[ j ][ 4 ];dp[ i ][ 3 ]+=dp[ j ][ 2 ];dp[ i ][ 4 ]+=dp[ j ][ 3 ];x1=min(x1,dp[ j ][ 0] -dp[ j ][ 3 ]);x2=min(x1,dp[ j ][ 1 ]-dp[ j ][ 2 ]);}dp[ i ][ 1 ]=dp[ i ][ 4 ]+x1;dp[ i ][ 2 ]=min(dp[ i ][ 3 ]+x2,min(dp[ i ][ 0 ],dp[ i ][ 1 ]));dp[ i ][ 3 ]=min(dp[ i ][ 2 ],dp[ i ][ 3 ]);dp[ i ][ 4 ]=min(dp[ i ][ 3 ],dp[ i ][ 4 ]);}printf("%d",dp[ 1 ][ 2 ]);return 0; }

覺得做完之后對于樹形DP有了新的認識 = =漲姿勢了

總結

以上是生活随笔為你收集整理的[HNOI]2003 消防局的建立的全部內容，希望文章能夠幫你解決所遇到的問題。

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