凸性证明

这道题的凸性没人证明，补一下。

其实是四边形不等式。本题目是区间分拆问题。设区间 $[l,r]$ 的成本为

本题问的是将区间 $[1,n]$ 拆成 $k$ 份并最小化上述成本的解 $ans$。最终答案就是 $k-ans$。

那么，问题的凸性只需要验证上述成本函数满足四边形不等式。直接验证二阶混合差分为负：

这显然成立。