邮局
加强版
加强加强版
普通版
\(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)\)。