「ZJOI2015」幻想乡 Wi-Fi 搭建计划

题目传送门

题目大意：有 个点要被 个圆覆盖，选择一个圆有一个代价，求最多有多少个点被覆盖与包含最多的点的情况下最小代价和。其中点分布在一个条带区域，圆的半径等于条带区域宽度。。

第一问很好做，直接 暴力过去即可。

对于第二问，先去掉不能被覆盖的点。

首先根据数据考虑圆只在一侧的情况，可以证明，每个圆包含的点是一段连续区间。因此对于单侧的情况，对点按 坐标排序后贪心选择就完事了，看起来暴力也可以。

我总觉得这个证明应该用到圆的半径为条带宽度这个性质……但是所有网上所有题解都没有……

如果是圆在两边，就只需要用 DP 把点分给两边的圆，注意到每边的圆覆盖的点仍然是一个连续的区间，因此记录上方和下方上一次转移的最后一个圆，然后转移即可。

记上方有 个圆，下方有 个圆。可知 。

时间复杂度为：，化简一下：

当且仅当 时等号成立。

因此时间复杂度是 的，空间复杂度是 的。

看起来时间有点爆炸，但是跑得很快……

代码见这里。