ZigZagK

Never give up fighting!

[wqs二分+DP]POJ1160【Post Office】题解

题目概述

\(n\) 个村庄,现在要建 \(m\) 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。

解题报告

显然是 \(O(n^2m)\) DP吧?数据小的可怜,这样就可以过了……

不过有一种更好的方法,可以把 \(m\) 优化到 \(log_2m\) ,这就是wqs(%%%Orz)二分了。

想法是这样的:去掉 \(f[i][j]\) (前 \(i\) 个村庄中建了 \(j\) 个邮局)中的 \(j\) ,枚举一个 \(cost\) 表示建邮局需要额外的 \(cost\) 花费,再记录一个 \(g[i]\) 表示前 \(i\) 个村庄在最优解的情况下最少建多少邮局。接下来刷DP,如果 \(g[n]\le m\) 就说明可行。由此可见 \(cost\) 是可以二分枚举的,所以我们就可以愉快的把 \(O(n^2m)\) 优化成 \(O(n^2log_2m)\)

严格的来说,只有当原函数 \(g(x)\) 的斜率单调,才可以这么处理。因为枚举 \(cost\) 实际上是一个逼近 \(g(x)\) 斜率的过程 \([g(x)-x\cdot cost]'=g'(x)-cost\) ,如果 \(g'(x)\) 不是单调的,就没办法二分枚举 \(cost\) 了。

还有要注意的是,最后并不一定刚好停在 \(m\) 个的位置,不过这并没有什么关系(反正答案是一样的),只不过算答案的时候不能用 \(f[n]-g[n]\cdot cost\) ,一定要用 \(f[n]-m\cdot cost\) ,因为题目要求的是 \(m\) 个。

另一道经典的wqs二分是BZOJ2654,那时候说这二分怎么这么神奇,原来是wqs二分QAQ。

示例程序

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

不资瓷Markdown;资瓷LaTeX:行内公式\(...\),行间公式\[...\]