P2279 [HNOI2003] 消防局的设立 题解加总结

思路因为题目求的是覆盖树上所有点的所放置最少的消防站数量因此此题需使用树形 DP 解决状态申明因为每个消防局能覆盖与它距离不超过 2 的节点 因此总共设有5个状态dp[x][0] 为覆盖到 的爷爷包括父亲和 整棵子树的最少个数dp[x][1] 为覆盖到 的父亲和 整棵子树的最少个数dp[x][2] 为覆盖 整棵子树的最少个数dp[x][3] 为覆盖所有 的儿子及其子树的最少个数dp[x][4] 为覆盖所有 的孙子及其子树的最少个数状态转移方程dp[x][0] 1dp[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][i1]因此就该跟新 dp[x][i1] 。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就让夕阳跌进梦里繁花落入谷底