这是我写的第10？个正式题解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 「HNOI2003」消防局的设立 题目链接 点这里 题目大意 定义 AAA 到 BBB 的距离 *** 为从 AAA 走到 BBB 最少经过的道路数量 要求设置若干消防站点，每个消防站点可以覆盖与其距离为 222 的所有节点 求覆盖所有节点所需最小消防站点数量 解题思路 1. 匹配算法 这题题目中有说到是“树状结构”，还要求求最小消防站点数量 所以是树形dp 2. 具体实现步骤 2.1 DP状态定义 因为我们发现与其距离为 222 相当于在树上覆盖了 * 爷爷 * 爸爸 * 自己 * 儿子 * 孙子 那么定义dp数组： dp[i][0]dp[i][0]dp[i][0] 代表 iii 这个位置放消防站，iii 的爷爷以及以 iii 为根节点的整棵子树全被覆盖的最少消防站点数量 dp[i][1]dp[i][1]dp[i][1] 代表 iii 这个位置不放消防站（iii 的儿子放消防站），iii 的父亲以及以 iii 为根节点的整棵子树全被覆盖的最少消防站点数量 dp[i][2]dp[i][2]dp[i][2] 代表 iii 这个位置不放消防站（iii 的孙子放消防站），以 iii 为根节点的整棵子树全被覆盖的最少消防站点数量 dp[i][3]dp[i][3]dp[i][3] 代表以 iii 的孩子为根节点的整棵子树全被覆盖的最少消防站点数量 dp[i][4]dp[i][4]dp[i][4] 代表以 iii 的孙子为根节点的整棵子树全被覆盖的最少消防站点数量 2.2 数学特征 经过定义，抛出一个概念：dp[i][0]≤dp[i][1]≤dp[i][2]≤dp[i][3]≤dp[i][4]dp[i][0] \le dp[i][1] \le dp[i][2] \le dp[i][3] \le dp[i][4]dp[i][0]≤dp[i][1]≤dp[i][2]≤dp[i][3]≤dp[i][4] 为什么，因为我们可以发现越是偏向 dp[i][4]dp[i][4]dp[i][4] 的那些状态，包含的范围就越小，则所需消防站点的数量一定是单调不减的 AC 代码