Vijos 1144 小胖守皇宫 解题报告

非常经典的皇宫守护问题，用树形DP即可求解。对于每个点的覆盖可以分三种情况讨论：

1. 在该点设守卫
2. 在子节点设守卫
3. 在父节点设守卫

分别用f[i,1],f[i,2],f[i,3]表示以上三种情况覆盖以该节点为根的子树所需的最少费用。则显然可以推出状态转移方程：

• f[i,1]=∑min(f[j,1],f[j,2],f[j,3])+v[i](j为i的子节点);
• f[i,2]=∑min(f[j,1],f[j,2])+mind(j为i的子节点;mind为所有子节点中f[j,1]-f[j,2]最小的，若存在f[j,1]<=f[j,2]则mind为0);对于叶节点，f[i,2]=v[i]。
• f[i,3]=∑f[j,2](j为i的子节点);

程序实现时用一个队列维护当前待处理的已经处理完全部叶节点的节点，最后加入队列中的节点就是根节点。

R1206607 Accepted 100 From IwfWcf－ P1144 FPC Vag 6K 2009-4-11 1:01:21

除非另有声明，本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 许可协议授权。