思路： 和“战略游戏”很像，但是状态明显变多了。 dp[i][0]代表i节点向上覆盖至i的父亲的父亲。 dp[i][1]代表i结点向上覆盖至i的父亲。 dp[i][2]代表i结点覆盖自身 dp[i][3]代表i结点向下覆盖自己的儿子。 dp[i][4]代表i结点向下覆盖自己的孙子。 状态方程大家可以看洛谷中的题解，这里不过多浪费时间了，给出一个参考代码，逻辑会稍微清晰一点。 代码有

传送门 解题思路：此题可以树形dp也可以贪心过，看了第一篇题解，非常nice！贪心的策略也很好想，我们从深度最大的开始，他没有孩子孙子，我们自然选择去建立他的祖父，这样可以覆盖到更多的点，我们如何去判断点是否已经被覆盖到了呢，可以开一个o数组 o[i]表示 i到最近的消防站的距离 初始化为 0x3f3f3f3f 。代码如下： #include<cstdio>#include<iostream

今天做dp的时候, 看见一道似曾相识的题 ---  [HNOI2003]消防局的设立 我的第一反应就是 UVa1292 Strategic game 这道题. 我以为, 这两题的差距只在"控制的距离上". 于是乎, 苦想dp无果(虽然这题可以dp). 看题解发现原来是简单的贪心. 解决了这道题以后, 我就回头研究UVa1292了. 在网上找了一圈, 发现没有用贪心做的. 我岂不是发现了一种新的做

纽约大概有一百万栋建筑，每年其中3千栋会起大火。官员们能够预测哪些楼会着火么？ 纽约市消防局认为他们可以利用数据挖掘来做到这点。消防局的分析员称某些建筑和一些更容易起火的因素有关联。 贫穷就是其一。 “低收入社区和火灾有相关性，” 消防局的分析主管Jeff Chen在拉斯维加斯上的一个工业会议上这样说道。 其他一些和致命火灾相关的因素有：建筑物的年龄，它有没有电路问题，洒水器的数量和位置，

题目描述 2020年，人类在火星上建立了一个庞大的基地群，总共有n个基地。起初为了节约材料，人类只修建了n-1条道路来连接这些基地，并且每两个基地都能够通过道路到达，所以所有的基地形成了一个巨大的树状结构。如果基地A到基地B至少要经过d条道路的话，我们称基地A到基地B的距离为d。 由于火星上非常干燥，经常引发火灾，人类决定在火星上修建若干个消防局。消防局只能修建在基地里，每个消防局有能力

消防局有DP做法，而且要是按省选难度看的话那个题应该是DP 昨天跟冯神讨论了一下，如果点上设权，那么就只能DP做了 下面DP部分的详细讲解转载自luogu CaptainSlow 的题解（这里是他的博客） DP[i][state] 表示 i 当前子树根节点state就是一个一个的状态state = 0, 1, 2 :DP[i][0] 表示 选 i 为消防局DP[i][1] 表示 {至少