思路
因为题目求的是覆盖树上所有点的所放置最少的消防站数量，因此此题需使用树形 DP 解决
状态申明
因为每个"消防局"能覆盖与它距离不超过 2 的节点 ，因此
总共设有5个状态
- dp[x][0] 为覆盖到 的爷爷（包括父亲）和 整棵子树的最少个数；
- dp[x][1] 为覆盖到 的父亲和 整棵子树的最少个数；
- dp[x][2] 为覆盖 整棵子树的最少个数；
- dp[x][3] 为覆盖所有 的儿子及其子树的最少个数；
- dp[x][4] 为覆盖所有 的孙子及其子树的最少个数；
状态转移方程
- dp[x][0] = 1
dp[y][4] （ 为 的孩子 ）
要覆盖到爷爷的话必须选 ，并贪心地选 的第五种状态
- dp[x][1] = min ( dp[y][0] +
dp[k][3] )（ 和 皆为 的孩子且
)
的儿子中有一个一定覆盖的爷爷，同时覆盖到兄弟（因为 一定是选了），其他的儿子只需要覆盖的自己的儿子即可
- dp[x][2] = min ( dp[y][1] +
dp[k][2] )（ 和 皆为 的孩子且
)
有一个儿子覆盖到父亲，但无法覆盖到 的兄弟，所以其他儿子要覆盖到自己
- dp[x][3] =
dp[y][2] （ 为 的孩子 ）
让每个儿子覆盖到自己
- dp[x][4] =
dp[y][3] （ 为 的孩子 ）
让每个儿子覆盖到自己的儿子
遍历顺序
由叶子节点到根
边界条件
- 叶子节点
dp[x][0] = dp[x][1] = dp[x][2] =1 ;
dp[x][3] = dp[x][4] = 0 ;
- 非叶子节点
dp[x][0] = 1 , dp[x][1] = dp[x][2] = ;
dp[x][3] = dp[x][4] = 0 ;
输出答案
dp[1][2]（根包含自己和所有子树的最小答案）
评估效率
时间复杂度： 空间复杂度：
注意
因为 dp[x][0] 的答案包含 dp[x][1 ~ 4] , dp[x][1] 的答案包含 dp[x][2 ~ 4]。同理，因此 dp[x][4] dp[x][3] dp[x][2] dp[x][1] dp[x][0] , 但如果 dp[x][i] < dp[x][i+1]，因此就该跟新 dp[x][i+1] 。
AC代码
点开有惊喜
__EOF__
- 本文作者：陈叙安
- 本文链接：P2279 [HNOI2003] 消防局的设立 题解加总结 - 陈叙安 - 博客园
- 关于博主：https://www.cnblogs.com/chenxuan11
- 版权声明：除特殊说明外，转载请注明出处～[知识共享署名-相同方式共享 4.0 国际许可协议]
- 声援博主：如果您觉得文章对您有帮助，可以点击文章右下角【推荐】一下。
分类: 题解
免责声明：本内容来自平台创作者，博客园系信息发布平台，仅提供信息存储空间服务。
推荐该文 关注博主关注博主 收藏本文 分享微信
陈叙安
粉丝 - 1 关注 - 1
+加关注
0
« 上一篇： 2025 csp_j 游忌
» 下一篇： 2025半期游忌
posted @ 2025-11-12 14:41 陈叙安 阅读(71) 评论(0) 收藏 举报
登录后才能查看或发表评论，立即 登录 或者 逛逛 博客园首页
P2279 [HNOI2003] 消防局的设立 题解加总结 _
2025-11-12 14:41710021854:22 ~ 7:16
题解
[ I you ]
博客已运行 : 317 天 13 时 22 分 10 秒 ღゝ◡╹)ノ♡
博客园 © 2004-2026 浙公网安备 33010602011771号 浙ICP备2021040463号-3
就让夕阳跌进梦里，繁花落入谷底
