今天回过头来看了看DP的斜率优化。应该有两种吧。我们就以BZOJ1010为例。
首先这道题很容易就想到DP方程 ： DP(i) = min(DP(j) + (sum(i) - sum(j) + i - j - 1 - L)^2)
然后我们枚举i,j就可以得到一个n^2的算法.
接下来我们对式子化简有两种 ：
1：假设k > j 并且k比j更优。那么我们首先要证明对于i+v这种状态来说，k还是更优，换句话说我们需要证明单调性。然后我们再对式子化简可得：
设W(i) = sum(i) + i , p = l+1;
则只需要满足 wi >= (dp[k]+(w[k]+p)^2-dp[j]-(w[j]+p)^2)/（2*（w[k]-w[j]));
维护队头直接这样维护就行了。维护队尾的时候要看成图，维护一个凸包就行了。
2：把和i , j 分别相关的放在一起，然后化简，发现还是维护一个凸包。队首维护一个关系式，队尾维护凸包。
原文：http://www.cnblogs.com/registerzxr/p/5142262.html