相关链接
题目传送门：http://www.tsinsen.com/A1342
参考代码：http://paste.ubuntu.com/23803611/
解题报告
这题乍看需要 $ O({n^2})$ 的DP的样子
然而可以用 Tree 这道题一样，给每一次转移附加一个值 $ k$
然后直接转移，记录一下转移了多少次，根据次数的多少来调整 $ k$
然后再用上决策单调性来优化DP的话
这样似乎就可以在 $ O(n{\log ^{\rm{2}}}n)$ 的时间复杂度内解决这个问题了！
值得一提的是，毛爷爷讲了一下这个方法的适用范围：
DP的那个函数必须是一个凸包
不过毛爷爷也说了：
只要拍一拍，拍不出错就行啦！
Would you be all in favour of exchanging hyperlinks?
You are my breathing in, I possess few blogs and occasionally run out from to post .