今天做dp的时候, 看见一道似曾相识的题 ---  [HNOI2003]消防局的设立

我的第一反应就是 UVa1292 Strategic game 这道题. 我以为, 这两题的差距只在"控制的距离上".

于是乎, 苦想dp无果(虽然这题可以dp). 看题解发现原来是简单的贪心.

解决了这道题以后, 我就回头研究UVa1292了. 在网上找了一圈, 发现没有用贪心做的.

我岂不是发现了一种新的做法?

果断码码码, 结果

好吧, 我冷静下来, 再认真的读了一遍这个题,.

果然, 发现了这两个题之间细小的差别 :

UVa1292的部分题干

 [HNOI2003]消防局的设立 的部分题干

和@HailJedi讨论了一下,

这两个条件看起来等价, 实则不同. 从图论角度来说, 前者可以看做非二分图的 最小点覆盖 问题, 而后者可以看做非二分图的 最小边覆盖 问题的变形.

前者的解决方法一般采用dp, 而后者的解决方法一般是贪心. 后者的贪心策略用在前者上是错误的.

设红色的为根节点, 那么根据 HNOI 一题的贪心策略,我们会选择蓝色的点, 假设每一个点"管辖"的范围是1, 那么所有点都被覆盖住了,但是两条橙色的边没有被覆盖,不满足 UVA 一题的条件

我反思了一下我的做题过程, 因为"记得"做过类似的题, 所以并没有仔细审题, 也没有仔细分析这一题的性质. 这就是问题所在. 假如我"忘记"之前做过的题, 认真分析这一题的条件, 那么贪心是不难想出来的.

所以, 考场上如果遇到自己见过的题, 一定不要高兴的太早, 必须确认模型完全相同后才能套用之前的做法.

差之毫厘, "异"之千里 --- 从 UVa1292 与 [HNOI2003]消防局的设立 的异同谈审题的重要性

原文：https://www.cnblogs.com/wsmrxc/p/9295116.html