Tag: zoj

做了一天，把此题AC了，看到网上用的算法很复杂，发个自己的出来。
思路：
1.如果城市全空，可以不管顺序，随便从哪里开始放“碉堡”，把“碉堡”射程里的城市标记下，后面的“碉堡”不放在这里即可得到结果。
2.但是如果城市中有“墙”的话，就不可以按照1的方法了，因为放置数量的多少与顺序是有关的，所以，怎样来确定这个顺序是很重要的。观察发现，城市里的空地按照领域中的“墙”的数量可以分为五种，即从0到4。再观察，可以得到这样一个结论：按邻域中墙的数目由多到少，往空地上安放“碉堡”，可以使数目最大！
于是按照这个结论，编程如下：
Continue reading “zoj_1002(Fire Net)的一个简单的解法”