Luogu分析四边形不等式优化 DP 。首先有一个显然的 DP ：设 $f[i][j]$ 表示前 $i$ 个村庄设了 $j$ 个邮局的最小值，容易得到 $f[i][j]=\min\{f[i-1][j],f[k][j-1]+dis(k+1,i)\}$ 。这里的 $dis(i,j)$ 指 $[i,j]$ 中设一个邮局的最小值。如果一段区间里要放一个邮局，显然放在中间是最优的。于是可以通过前缀和 ...