ZJOI2015 BZOJ4092 幻想乡Wifi搭建计划

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

题意

平面上有一个长无限，宽为[tex]R[/tex]的长方形，内部有[tex]n[/tex]个点。

有[tex]m[/tex]个圆心在长方形上方或下方的圆，半径均为[tex]R[/tex]，每个圆有独立的权值。

球圆对点的最小权覆盖。

[tex]n,m\le 100[/tex]。

题解

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

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

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

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

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

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

令[tex]f[i][j][k][/tex]表示排过序的前[tex]i[/tex]个点，最后用到的上方和下方的圆分别为[tex]j,k[/tex]的最优值。

如果[tex]i+1[/tex]被[tex]j,k[/tex]覆盖，直接转移。

然后枚举圆[tex]l[/tex]转移到[tex]f[i][j][l],f[i][l][k][/tex]。

这样搞一下就好了...

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

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

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