斜率DP
如bzoj4518征途
f[i]=f[j]+(sum[i]-sum[j])^2;
決策j<k，要求最小值，因此當決策k優于決策j時
f[k]-2*s[i]*s[k]+s[k]^2 < f[j]-2*s[i]*s[j]+s[j]^2
即
(f[k]+s[k]^2)-(f[j]+s[j]^2) < 2*s[i] * (s[k]-s[j]) ①
滿足此式表明后面的點優于前面的點

出隊：隊頭后移直到①式不滿足，說明這個點是最優點
入隊：k越小越優，令x<y<z
如果k(x,y)>k(x,z)那么y出隊，（也可表達為k(x,y)>k(y,z)）
意思是x與z會比x與y更優，斜率更小，因此y沒有必要入隊
因為斜率越小越優，所以隊列里的斜率是遞增的，因此整個圖像是開口向上的二次函數。

對于斜率優化dp：

1、當方程涉及求和與平方時考慮可以優化，最后的形式是比較兩點的決策優先度可轉化為看斜率，比如此題求最小值，所以一斜率小于2*s[i]表明k比j越優

2、做此類題，首先簡化題目要求，比如本體答案可以轉化；然后列出方程和比較不等式，即令j<k，然后w[k]<w[j]（假如求最小值的話），得到斜率的不等式；

3、判斷出隊情況，比如當隊列前后的k都小于2*s[i]，表明后面的點始終比前面優

4、判斷入隊情況，比如k(x,z)<k(x,y)則z點比y點優

此類題的標志：

一般是將長度為n東西分成k段，每段的權值是以乘積或平方的形式出現

如果沒要求分段，那么O（n）就可以做

否則O（n*k）

轉載于:https://www.cnblogs.com/mzl120918/p/6406517.html

總結

以上是生活随笔為你收集整理的斜率DP复习总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。