[HNOI2003]消防局的设立 树形dp/贪心

f[root][能覆盖向上几层-2] = 需要消防站数

转移过程很巧妙，38行这一句加上以后：10-〉100

for(int i = 3;i >= 0;i--)f[s][i] = min(f[s][i],f[s][i+1]);

作用：维护最优性。（i guess）

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<vector>
 4 #include<cstring>
 5 using namespace std;
 6 typedef long long ll;
 7
 8 const int Maxn = 1010;
 9 vector<int> e[Maxn];
10 int f[Maxn][5];//f[i][j]向上j-2层 
11 int n,x;
12
13 void dfs(int s){
14     if(!e[s].size()){
15         f[s][2] = f[s][3] = f[s][4] = 1;
16         return;
17     }
18     for(int i = 0;i < e[s].size();i++){
19         int to = e[s][i];
20         dfs(to);
21         f[s][0] += f[to][1];
22         f[s][1] += f[to][2];
23         f[s][4] += f[to][0];
24     }
25     f[s][2] = f[s][3] = 1<<30;
26     for(int i = 0;i < e[s].size();i++){
27         int to = e[s][i],s2 = f[to][3],s3 = f[to][4];
28         for(int j = 0;j < e[s].size();j++){
29             int tt = e[s][j];
30             if(to == tt)continue;
31             s2 += f[tt][2];
32             s3 += f[tt][1];
33         }
34         f[s][2] = min(f[s][2],s2);
35         f[s][3] = min(f[s][3],s3);
36     }
37     f[s][4]++;
38     for(int i = 3;i >= 0;i--)f[s][i] = min(f[s][i],f[s][i+1]);
39 }
40
41 int main(){
42     cin >> n;
43     for(int i = 2;i <= n;i++){
44         cin >> x;
45         e[x].push_back(i);
46     }
47     dfs(1);
48     cout << f[1][2];
49 return 0;
50 }

View Code

 参考：https://www.luogu.org/blog/rickole/solution-p2279