该题有两种做法,树形\(DP\)和贪心。
先讲贪心。
先将所有点按深度从大到小排序,然后从大到小依次取出点,若已经被覆盖则跳过,否则就在它的祖父点建立消防站。
考虑如何判断该点是否被覆盖,设数组\(dis[x]\)表示点\(x\)到达离它最近的消防站的距离。
则在扫到一个点时,先用它父亲和祖父的\(dis\)来尝试更新该点的\(dis\),即尝试用父亲或祖父来覆盖该点,若没有被覆盖,则在祖父建立消防站,并更新祖父的父亲和祖父的祖父的\(dis\),这样就能同时将兄弟节点和儿子(孙子)节点覆盖点的情况记录下来。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010;
int de[N], fa[N], po[N], dis[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
bool comp(int x, int y)
{
return de[x] > de[y];
}
int main()
{
int i, x, y, z, n, s = 0;
n = re();
memset(dis, 60, sizeof(dis));
for (de[1] = po[1] = 1, i = 2; i <= n; i++)
{
scanf("%d", &fa[i]);
de[i] = de[fa[i]] + 1;
po[i] = i;
}
sort(po + 1, po + n + 1, comp);
for (i = 1; i <= n; i++)
{
x = po[i];
y = fa[x];
z = fa[y];
dis[x] = minn(dis[x], minn(dis[y] + 1, dis[z] + 2));
if (dis[x] > 2)
{
dis[z] = 0;
s++;
x = fa[z];
y = fa[x];
dis[x] = minn(dis[x], 1);
dis[y] = minn(dis[y], 2);
}
}
printf("%d", s);
return 0;
}
然后是另一种做法,树形\(DP\)。
设\(f[x][k]\)表示以\(x\)为根的子树,\(x\)点在\(k\)状态下建立的消防局总数。
前\(3\)种情况保证\(x\)被覆盖,后\(2\)种则不能保证。
设\(y,z\)均为\(x\)儿子。
则有状态转移方程:
显然对于状态\(0\to 4\),建立的消防局总数依次减小,所以可以优化转移方程:
最后答案就是\(f[1][2]\)。
因为贪心的可拓展性较好(可以处理覆盖\(k\)距离的情况),且打起来简单,所以这里就不给出\(DP\)的代码了(其实是懒)。
原文:https://www.cnblogs.com/Iowa-Battleship/p/9832396.html