洛谷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]$

 #include<cstdio>

 #include<cstdlib>

 #include<map>

 #include<set>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<stack>

 #include<queue>

 #include<iostream>

 #define inf 0x3f3f3f3f

 using namespace std;

 typedef long long LL;

 typedef pair<int, int> pr;

 int n;

 const int maxn = ;

 int fa[maxn];

 vector<int>son[maxn];

 int dp[maxn][];

 void dfs(int rt)

 {

     if(son[rt].size() == ){

         dp[rt][] = ;

         dp[rt][] = dp[rt][] = inf;

         dp[rt][] = dp[rt][] = ;

         return;

     }

     dp[rt][] = ;

     int maxson = inf, maxgs = inf;

     for(int i = ; i < son[rt].size(); i++){

         dfs(son[rt][i]);

         int tmp1 = inf, tmp2 = inf, tmp3 = inf;

         for(int j = ; j < ; j++){

             tmp1 = min(tmp1, dp[son[rt][i]][j]);

             if(j < )tmp2 = min(tmp2, dp[son[rt][i]][j]);

             if(j < )tmp3 = min(tmp3, dp[son[rt][i]][j]);

         }

         dp[rt][] += tmp1;

         dp[rt][] += tmp2;

         maxson = min(maxson, dp[son[rt][i]][] - tmp2);

         maxgs = min(maxgs, dp[son[rt][i]][] - tmp3);

         dp[rt][] += tmp3;

         dp[rt][] += tmp3;

         dp[rt][] += tmp2;

     }

     dp[rt][] += maxson;

     dp[rt][] += maxgs; 

 }

 int main()

 {

     scanf("%d", &n);

     for(int i = ; i <= n; i++){

         scanf("%d", &fa[i]);

         son[fa[i]].push_back(i);

     }

     dfs();

     printf("%d\n", min(dp[][], min(dp[][], dp[][])));

 }

巴特西

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

最新文章

热门文章