题解 P2279 【[HNOI2003]消防局的设立】
CaptainSlow
2017-10-09 13:34:53
##写一个稍微好理解一点的题解
身为**蒟蒻**，看懂题意之后，明白了是一个树形动规，不过方程不太清楚。然后看了题解，看不懂~~~
最后历经十八弯终于搞懂了树形DP的思路（**就是不写贪心，不写贪心！！！**）。
由于在我看来之前的题解都不易理解，来当个好人，写一个蒟蒻们绝对看得懂的题解。
###树形DP不必解释了吧
下面讲一讲状态：
```cpp
DP[i][state] 表示 i 当前子树根节点
state就是一个一个的状态
state = 0, 1, 2 :
DP[i][0] 表示 选 i 为消防局
DP[i][1] 表示 {至少} 选了 i 的一个儿子为消防局
DP[i][2] 表示 {至少} 选了 i 的一个孙子为消防局
==================================以上三种状态是 i {一定被消防局覆盖} 的情况
state = 3, 4 :
DP[i][3] 表示 i 的 {所有} 儿子节点一定被消防局覆盖
DP[i][4] 表示 i 的 {所有} 孙子节点一定被消防局覆盖
==================================以上两种状态是 i {不一定被消防局覆盖} 的情况
```
然后讲转移
**（画棵树模拟一下理解得快些）**
```cpp
初始方程：
（以下j, k均表示i的儿子节点）
DP[i][0] = 1 + Σ min ( DP[j][0...4] );
由于当 i 为消防站之后儿子和孙子是否为消防局就无关紧要，因此状态在0~4中寻找一个MIN，然后还需要+1（因为自己是消防局）
DP[i][1] = min ( DP[k][0] + Σ ( j != k ) min ( DP[j][0...3] ) );
由于儿子为消防站时只能覆盖到兄弟（这里不含所选儿子的儿子），要使选了一个儿子之后子树中包括自己的所有节点都被覆盖，所以除了这个选的儿子，其他儿子的儿子一定要全部被覆盖，状态0~3满足。
DP[i][2] = min ( DP[k][1] + Σ ( j != k ) min ( DP[j][0...2] ) );
要使选了一个孙子之后合法，由于孙子最多只能覆盖到当前节点，所以其他儿子一定全部覆盖， 状态0~2满足
DP[i][3] = Σ min(DP[j][0...2]);
要使儿子及孙子全部被覆盖，即儿子本身要被覆盖，状态0~2满足
DP[i][4] = Σ min(DP[j][0...3]);
孙子全部被覆盖 ，状态0~3满足
```
然后可以简化：（加速）（推到过程很简单，可以看我的代码一起理解，如果你明白了上面的方程这里就是小菜一碟了）
```cpp
令 DP[i][j] 表示 min ( DP[i][0..k] ) (2<=k<=4)
因此可以得到：
DP[i][0] = 1 + Σ DP[j][4];
DP[i][1] = DP[i][4] + min ( DP[k][0] - DP[k][3] );
DP[i][2] = DP[i][3] + min ( DP[k][1] - DP[k][2] );
DP[i][3] = Σ DP[j][2];
DP[i][4] = Σ DP[j][3];
```
然后具体实践时还有一些小技巧，我的DP用递推实现
附代码：
```cpp
const
INF=maxlongint;
var
firap,last,point,next:array[0..1010]of longint;
n,i,ai,e:longint;
f:array[0..1000,0..4]of longint;
function min(n1,n2:longint):longint;
begin
if (n1<n2) then exit(n1) else exit(n2);
end;
procedure dp(now:longint);
var x1,x2,j,pj:longint;
begin
if ((firap[now]=-1) and (now<>1)) then //特判（可能快些？）
begin
for j:=0 to 2 do f[now,j]:=1;
for j:=3 to 4 do f[now,j]:=0;
exit;
end;
x1:=INF;
x2:=INF;
f[now][0]:=1;
j:=firap[now];
while (j<>-1) do
begin
pj:=point[j];
dp(pj);
inc(f[now,0],f[pj,4]);
inc(f[now,3],f[pj,2]);
inc(f[now,4],f[pj,3]);
x1:=min(x1,f[pj,0]-f[pj,3]);
x2:=min(x2,f[pj,1]-f[pj,2]);
j:=next[j];
end;
f[now,1]:=f[now,4]+x1;
f[now,2]:=min(f[now,3]+x2,min(f[now,0],f[now,1]));
f[now,3]:=min(f[now,2],f[now,3]);
f[now,4]:=min(f[now,3],f[now,4]);
end;
begin
fillchar(firap,sizeof(firap),255);
filldword(last,sizeof(last) div 4,0);
fillchar(next,sizeof(next),255);
read(n);
for i:=2 to n do
begin
read(ai);
e:=i-1;
if (firap[ai]=-1) then firap[ai]:=e;
next[last[ai]]:=e;
point[e]:=i;
last[ai]:=e; //邻接表存边，读题意可以明白父节点编号一定小于该子节点编号
end;
dp(1);
writeln(f[1][2]); //输出F[1][2]，贪心思路
end.
```
参考资料：**（灰常感谢啊）**
@Crazyxx 在题解中最早写的一个思路
[某犇写的灰常易懂题解](http://www.cnblogs.com/QWsin/p/5306197.html)（他也参照了Crazyxx的思路，我的题解是在他写的之上整理而成）