我們知道，有些DP方程可以轉化成DP[i]=f[j]+x[i]的形式，其中f[j]中儲存了隻與j相關的量。這樣的DP方程我們可以用單調隊列進行優化，進而使得O(n^2)的複雜度降到O(n)。
可是并不是所有的方程都可以轉化成上面的形式，舉個例子：dp[i]=dp[j]+(x[i]-x[j])*(x[i]-x[j])。如果把右邊的乘法化開的話，會得到x[i]*x[j]的項。這就沒辦法使得f[j]裡隻存在于j相關的量了。于是上面的單調隊列優化方法就不好使了。
這裡學習一種新的優化方法，叫做斜率優化，其實和凸包差不多，下面會解釋。
舉例子說明是最好的！HDU 3507，很适合的一個入門題。
大概題意就是要輸出N個數字a[N]，輸出的時候可以連續連續的輸出，每連續輸出一串，它的費用是 “這串數字和的平方加上一個常數M”。
我們設dp[i]表示輸出到i的時候最少的花費，sum[i]表示從a[1]到a[i]的數字和。于是方程就是：
dp[i]=dp[j]+M+(sum[i]-sum[j])^2；
很顯然這個是一個二維的。題目的數字有500000個，不用試了，二維鐵定逾時了。那我們就來試試斜率優化吧，看看是如何做到從O(n^2)複雜度降到O(n)的。
分析:
我們假設k<j<i。如果在j的時候決策要比在k的時候決策好，那麼也是就是dp[j]+M+(sum[i]-sum[j])^2<dp[k]+M+(sum[i]-sum[k])^2。(因為是最小花費嘛，是以優就是小于)
兩邊移項一下，得到：(dp[j]+num[j]^2-(dp[k]+num[k]^2))/(2*(num[j]-num[k]))<sum[i]。我們把dp[j]-num[j]^2看做是yj，把2*num[j]看成是xj。
那麼不就是yj-yk/xj-xk<sum[i]麼？ 左邊是不是斜率的表示？
那麼yj-yk/xj-xk<sum[i]說明了什麼呢？ 我們前面是不是假設j的決策比k的決策要好才得到這個表示的？
如果是的話，那麼就說明g[j,k]=yj-jk/xj-xk<sum[i]代表這j的決策比k的決策要更優。
關鍵的來了：現在從左到右，還是設k<j<i，如果g[i,j]<g[j,k]，那麼j點便永遠不可能成為最優解，可以直接将它踢出我們的最優解集。為什麼呢？
我們假設g[i,j]<sum[i]，那麼就是說i點要比j點優，排除j點。
如果g[i,j]>=sum[i]，那麼j點此時是比i點要更優，但是同時g[j,k]>g[i,j]>sum[i]。這說明還有k點會比j點更優，同樣排除j點。
排除多餘的點，這便是一種優化！
接下來看看如何找最優解。
設k<j<i。
由于我們排除了g[i,j]<g[j,k]的情況，是以整個有效點集呈現一種上凸性質，即k j的斜率要大于j i的斜率。
這樣，從左到右，斜率之間就是單調遞減的了。當我們的最優解取得在j點的時候，那麼k點不可能再取得比j點更優的解了，于是k點也可以排除。換句話說，j點之前的點全部不可能再比j點更優了，可以全部從解集中排除。
于是對于這題我們對于斜率優化做法可以總結如下：
1，用一個單調隊列來維護解集。
2，假設隊列中從頭到尾已經有元素a b
c。那麼當d要入隊的時候，我們維護隊列的上凸性質，即如果g[d,c]<g[c,b]，那麼就将c點删除。直到找到g[d,x]>=g[x,y]為止，并将d點加入在該位置中。
3，求解時候，從隊頭開始，如果已有元素a b
c，當i點要求解時，如果g[b,a]<sum[i]，那麼說明b點比a點更優，a點可以排除，于是a出隊。最後dp[i]=getDp(q[head])。
View Code
源自：