洛谷P2279 消防局的设立【树形dp】

题目：https://www.luogu.org/problemnew/show/P2279

题意：一棵树。在节点处建消防站，可以覆盖与他距离在2之内的节点。问最少要建多少个消防站，可以覆盖所有的节点。

思路：有一种贪心的思路，看大部分题解都是这样。

如果要覆盖当前节点（自己不建），那么可能是父亲，兄弟，祖父建了。

但是我们发现，在祖父建覆盖的范围比父亲兄弟要更广一些。所以就贪心的取深度最深的节点，在他的祖父处建一个。

因为想练dp所以没写贪心的。

看结构感觉是树形dp。$dp[i]$表示以$i$为根的子树的情况，想再开一维表示$i$有没有建。后来发现状态好像并不够。

因为只考虑子树的话，当前节点$i$不被覆盖也没关系，他可以被他的父亲或祖先覆盖。

所以大情况分成两种，$i$被覆盖和$i$没被覆盖。

其中$i$被覆盖可以是因为$i$自己建了，也可以是因为有一个儿子建了或者是有一个孙子建了。所以这里有三种状态。

$i$没被覆盖还可以分成只有$i$没被覆盖和$i$和儿子都没有被覆盖。这里又是两种状态。

所以总共是5中状态：

$dp[i][0]，在i处建$

$dp[i][1], i处不建但i至少有一个儿子建了$

$dp[i][2]，i和儿子都不建但至少有一个孙子建了$

$dp[i][3]，自己还没被覆盖，儿子已经被覆盖$

$dp[i][4], 自己和儿子都还没被覆盖$

转移方程：

$dp[i][0] = 1 + sum min(dp[son][0...4])$每一个儿子的任何一种状态都可以。所以每个儿子都取5种状态的最小的。

$dp[i][1] = min(dp[son1][0] + sum_(son != son1) min(dp[son][0...3]))$，这里一个巧妙的处理方法是先将每一个儿子的$min(dp[son][0...3])$加上，在找到最小的$dp[son][0]-min(dp[son][0...3])$最后加上。

$dp[i][2] = min(dp[son1][1] + sum_(son!=son1)(min(dp[son][0...2]))$，此时如果son不在子树被覆盖的话，别的节点也reach不到了。处理方法和上面也一样。

$dp[i][3] = sum min(dp[son][0...2])$

$dp[i][4] = sum min(dp[son][0...3]$

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<map>
 4 #include<set>
 5 #include<cstring>
 6 #include<algorithm>
 7 #include<vector>
 8 #include<cmath> 
 9 #include<stack>
10 #include<queue>
11 #include<iostream>
12 
13 #define inf 0x3f3f3f3f
14 using namespace std;
15 typedef long long LL;
16 typedef pair<int, int> pr;
17 
18 int n;
19 const int maxn = 1005;
20 int fa[maxn];
21 vector<int>son[maxn]; 
22 int dp[maxn][6];
23 
24 void dfs(int rt)
25 {
26     if(son[rt].size() == 0){
27         dp[rt][0] = 1;
28         dp[rt][1] = dp[rt][2] = inf;
29         dp[rt][3] = dp[rt][4] = 0;
30         return;
31     }
32     dp[rt][0] = 1;
33     int maxson = inf, maxgs = inf;
34     for(int i = 0; i < son[rt].size(); i++){
35         dfs(son[rt][i]);
36         int tmp1 = inf, tmp2 = inf, tmp3 = inf;
37         for(int j = 0; j < 5; j++){
38             tmp1 = min(tmp1, dp[son[rt][i]][j]);
39             if(j < 4)tmp2 = min(tmp2, dp[son[rt][i]][j]);
40             if(j < 3)tmp3 = min(tmp3, dp[son[rt][i]][j]);
41         }
42         dp[rt][0] += tmp1; 
43         dp[rt][1] += tmp2;
44         maxson = min(maxson, dp[son[rt][i]][0] - tmp2);
45         maxgs = min(maxgs, dp[son[rt][i]][1] - tmp3);
46         dp[rt][2] += tmp3;
47         dp[rt][3] += tmp3;
48         dp[rt][4] += tmp2;
49     }
50     dp[rt][1] += maxson;
51     dp[rt][2] += maxgs; 
52     
53 }
54 
55 int main()
56 {
57     scanf("%d", &n);
58     for(int i = 2; i <= n; i++){
59         scanf("%d", &fa[i]);
60         son[fa[i]].push_back(i); 
61     }
62     dfs(1);
63     printf("%d
", min(dp[1][0], min(dp[1][2], dp[1][1])));
64     
65 }