ZJOI2015 BZOJ4092 幻想乡Wifi搭建计划

其实很水的一道题...但感觉思路还是很神...总之我这个sb就是想不到...

题意

平面上有一个长无限，宽为的长方形，内部有个点。

有个圆心在长方形上方或下方的圆，半径均为，每个圆有独立的权值。

球圆对点的最小权覆盖。

。

题解

既然最小权覆盖是NPC的肯定有什么奇怪性质咯...就跟文学那题一样...

听说线性规划姿势好可以90分？

如果所有的圆都在长方形上方怎么搞？

注意到所有圆半径相等，因此我们将所有的点按横坐标排序。那么最优方案中每个圆覆盖的点一定是连续的一段。

因此，排个序直接贪心就好了。

现在圆分为上下两部分，我们用一个dp来分配它们。

令表示排过序的前个点，最后用到的上方和下方的圆分别为的最优值。

如果被覆盖，直接转移。

然后枚举圆转移到。

这样搞一下就好了...

这样虽然会有不合法的情况但最优解一定是合法的...这个可以由前面的贪心证明...

于是这题就做完了...比想象中的水多了...

(还有为毛我的程序跑得这么慢T_T)