消防局的设立

题目描述

$2020$年,人类在火星上建立了一个庞大的基地群,总共有n个基地。起初为了节约材料,人类只修建了$n-1$条道路来连接这些基地,并且每两个基地都能够通过道路到达,所以所有的基地形成了一个巨大的树状结构。如果基地$A$到基地$B$至少要经过$d$条道路的话,我们称基地$A$到基地$B$的距离为$d$。

由于火星上非常干燥,经常引发火灾,人类决定在火星上修建若干个消防局。消防局只能修建在基地里,每个消防局有能力扑灭与它距离不超过$2$的基地的火灾。

你的任务是计算至少要修建多少个消防局才能够确保火星上所有的基地在发生火灾时,消防队有能力及时扑灭火灾。

输入文件的第一行为$n (n\le 1000)$,表示火星上基地的数目。接下来的$n-1$行每行有一个正整数,其中文件第$i$行的正整数为$a[i]$,表示从编号为i的基地到编号为$a[i]$的基地之间有一条道路,为了更加简洁的描述树状结构的基地群,有$a[i]<i$。

贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
bool comp(int a, int b){ return dep[a] > dep[b];}

void MIN(int &a, int b){ a = min(a, b);}
//今天也是乱写函数的一天

int main(){
n = read();
fa[1] = 1;//注意这里,不然fa[1] = 0 会出锅
order[1] = 1;
near[1] = MAXN;//near存储离i最近的消防局到i的距离
for(int i = 2; i <= n; ++ i) {
fa[i] = read(), dep[i] = dep[fa[i]] + 1;
order[i] = i, near[i] = MAXN;
}//所以说这道题的输入数据很神奇啊
sort(order + 1, order + n + 1, comp);
//按照深度sort!
//这样的贪心就一定没问题了
for(int i = 1; i <= n; ++ i){
int now = order[i], fat = fa[now], grand = fa[fat];
MIN(near[now], min(near[fat] + 1, near[grand] + 2));
//这样处理就不用考虑兄弟节点了
//很妙啊
if(near[now] > 2){
//如果方圆2单位距离内没有消防局,就在该点的爷爷节点设立消防局
//多明显的贪心啊然后我还没有想出来
near[grand] = 0;
MIN(near[fa[grand]], 1);
MIN(near[fa[fa[grand]]], 2);
//更新祖先节点们的near
++ ans;
}
}
//还有就是似乎这样贪心比DP的普适度更好(?)
printf("%d", ans);
return 0;
}

树形DP

第一眼也觉得是考这个
然后发现似乎有五种甚至以上的情况
不但推不出来还把自己绕死在里面了
幸好有这样做的题解
实现得超级优秀


首先我们需要第二维大小为5的f数组

$f[i][0]:i$节点建了消防局
$f[i][1]:i$有至少一个子节点建了消防局
$f[i][2]:i$有至少一个孙子节点建了消防局

—注意:以上三种是保证了i被覆盖的—

$f[i][3]:i$的儿子节点全都被覆盖
$f[i][4]:i$的孙子节点全都被覆盖

—注意:以上两种是不保证i被覆盖的—

至于为什么要这样定义3和4,要看下面的转移方程:
(其中的$“a…b”$表示在$f[j][a]…f[j][b]$中取$min$)

$f[i][0] = 1 + \sum{f[j][0…4]}$

$i$节点建立了消防局,那么儿子节点和孙子节点都会被覆盖,只需要保证曾孙节点被覆盖,所以在$f[j][0…4]$中取$min$转移

$f[i][1] = f[k][0] + \sum{f[j][0…3](j != k)}$

$i$的某一个子节点建立了消防局,那么$i$的所有子节点都会被覆盖,只需要保证孙子节点也就是子节点的儿子节点被覆盖,所以在$f[j][0…3]$中取$min$转移

$f[i][2] = f[k][1] + \sum{f[j][0…2](j != k)}$

不能保证$i$的子节点被覆盖,所以在$f[j][0…2]$中取$min$转移

$f[i][3] = \sum{f[j][0…2]}$
$f[i][4] = \sum{f[j][0…3]}$

注意对于$f[i][4]$的理解

然后我们发现还可以做很多优化来降低状态转移方程的复杂度
①简化取$min$操作

$f[i][1] = min(f[j][0] - f[j][0…3]) +\sum{f[j][0…3]}$
$f[i][2] = min(f[j][1] - f[j][0…2]) + \sum{f[j][0…2]}$

②利用方程中的相同项

$f[i][1] = min(f[j][0] - f[j][0…3]) + f[i][4]$
$f[i][2] = min(f[j][1] - f[j][0…2]) + f[i][3]$

③取$min$意义下的合并

定义 $f[i][a]$ 替代原来的 $f[i][0…a]$
由状态转移方程看出只能对$a \ge 2$处理,因为$f[j][1]$没有跟$f[j][0]$取$min$的操作,它都是单独出现的

然后这样写起来就不难了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void MIN(int &a, int b){ a = min(a, b);}

int main(){
n = read();
for(int i = 2; i <= n; ++ i) {
m = read();
add(m, i);//m是i的父亲节点
}
for(int i = n; i >= 1; -- i){
//输入数据保证了编号大的节点一定不会是编号小的节点的前辈
max1 = max2 = MAXN;
f[i][0] = 1;//+1
for(int j = head[i]; j; j = ne[j]){
int To = to[j];
f[i][0] += f[To][4];
f[i][3] += f[To][2];
f[i][4] += f[To][3];
MIN(max1, f[To][0] - f[To][3]);
MIN(max2, f[To][1] - f[To][2]);
}
f[i][1] = f[i][4] + max1;//不取min
f[i][2] = min(f[i][3] + max2, min(f[i][1], f[i][0]));
MIN(f[i][3], f[i][2]);
MIN(f[i][4], f[i][3]);//取min
}
printf("%d", f[1][2]);//f[1][0...2]都是保证了所有节点被覆盖的
return 0;
}

日常

昨天晚上做噩梦了
梦见深山老林里的收尸人老婆婆(?)和她开的饭店
饭店名字记不清了,但非常不友好
甚至还梦见关于她的二儿一女
小儿子死在了某个地方
女儿为了找小儿子所以回到家乡一直跟在大儿子身边
或许那个小儿子是她的情人什么的?
记不清了啊
太诡异了