P6246 邮局 题解

邮局
加强版
加强加强版

普通版

$dp_{i, k} = \min_{j=0}^{i-1}dp_{j, k - 1} + w(j + 1, i)$
其中 $dp_{i, k}$ 表示前 $i$ 个放 $k$ 个邮局的最小代价，$w(l, r)$ 表示 $[l, r]$ 放一个邮局的最小代价。
考虑怎么求 $w(l, r)$，显然放邮局最优在第 $\left\lfloor\frac{l+r}{2}\right\rfloor$ 个点，我们设为 $x$。

$$\begin{aligned} w(l, r) &= \sum_{i=l}^{x-1} a_x-a_i + \sum_{i=x+1}^r a_i-a_x\\ &= (x-l)a_x - \sum_{i=l}^{x-1}a_i +\sum_{i=x+1}^r a_i - (r-x)a_x\\ &= (x-l)a_x - (S_{x-1} - S_{l-1}) + (S_r - S_x) - (r-x)a_x\\ \end{aligned}$$

直接暴力转移是 $O(kn^2)$，可以过普通版。

加强版

考虑优化这个 DP，式子中的 $x$ 难以在斜率优化中计算。
而这个式子显然满足决策单调性，因为 $w(l, r + 1) \le w(l + 1, r + 1)$。
所以我们可以用决策单调性优化到 $O(kn\log n)$。

加强加强版

我们在复杂度上还没优化 $k$。
注意到此题恰好分 $k$ 段，且满足四边形不等式。
我们在式子中加入常数 $c$，用 wqs 二分优化到 $O(n\log n\log k)$。