題目我就不再贅述了，題目傳送門

首先我們先來了解一下斜率優化的用處：斜率優化就是把一些特殊的dp方程化簡、變形，然后用維護單調隊列，把O(n^2)的時間復雜度降至O(n)，實現程序的提速。

當然有些dp方程是無法用斜率優化的，這個我等下會進行詳細解釋的。

題目中最基本的dp方程可以很容易的想到：f[i]=min{f[j]+(i-(j+1)+s[i]-s[j]-L)^2} (0<=j<i) 其中s[i]表示Sigma(c[k]) (1<=k<=i)

我們設p[i]=s[i]+i，M=L+1，則原方程可以轉化成f[i]=min{f[j]+(p[i]-p[j]-M)^2} (0<=j<i)

則：f[i]=min{f[j]+p[i]^2-2*p[i]*(p[j]+M)+(p[j]+M)^2} (0<=j<i)

若k<j且j的決策比k要好，則：f[j]+p[i]^2-2*p[i]*(p[j]+M)+(p[j]+M)^2<f[k]+p[i]^2-2*p[i]*(p[k]+M)+(p[k]+M)^2

化簡，得：f[j]+(p[j]+M)^2-f[k]+(p[k]+M)^2<2*p[i]*(p[j]-p[k])

不等式兩邊同時除以2*(p[j]-p[k])，得：(f[j]+(p[j]+M)^2-f[k]+(p[k]+M)^2)/(2*(p[j]-p[k]))<p[i] 

(f[j]+(p[j]+M)^2-f[k]+(p[k]+M)^2)/(2*(p[j]-p[k]))就是斜率g(j,k)

因為s[i]是嚴格單調上升的，所以p[i]也是嚴格單調上升的。若p[i]不是嚴格單調上升的，那么原dp方程就無法用斜率優化，因為原dp方程不滿足單調隊列的單調性。

所以，知道g(j,k)后，我們可以O(1)判斷出j比k更優。

但是，知道g(j,k)后我們并不能把時間復雜度降到O(n)，我們還需要一個強有力的幫手：單調隊列。

dui[]表示單調隊列，t為隊頭，w為隊尾。

1、循環，若g(dui[t+1],dui[t])<p[i]，說明dui[t+1]這個決策對于i來說要比dui[t]優，又因為p[i]是嚴格單調上升的，所以dui[t]這個決策對于后面的所有狀態均不產生影響，因此可以將dui[t]彈出單調隊列。循環結束后，可根據dui[t]算得f[i]。

2、循環，若g(i,dui[w])<g(dui[w],dui[w-1])：

1）若g(i,dui[w])<g(dui[w],dui[w-1])<p[i]，可得g(i,dui[w])<p[i]，所以決策i要優于決策dui[w]，所以dui[w]這個決策對于后面的所有狀態均不產生影響，因此可以將dui[w]彈出單調隊列。

2）若p[i]<g(i,dui[w])<g(dui[w],dui[w-1])，可得決策dui[w]優于決策i，決策dui[w-1]優于決策dui[w]，所以dui[w]這個決策對于后面的所有狀態同樣均不產生影響，因此可以將dui[w]彈出單調隊列。

綜上所述，首先求出斜率g(j,k)，然后維護單調隊列，依次算出f[]，答案即為f[n]。

附上AC代碼：

#include <cstdio>using namespace std; long long n,m,a[50010],s[50010],f[50010],p[50010],dui[50010],t,w; long long min(long long a,long long b){    return a<b?a:b;} long long calc(int x,int y){    return (f[x]+(p[x]+m)*(p[x]+m)-f[y]-(p[y]+m)*(p[y]+m))/(2*(p[x]-p[y]));} int main(void){    scanf("%lld%lld",&n,&m);++m;    for (int i=1; i<=n; ++i)        scanf("%lld",&a[i]),s[i]=s[i-1]+a[i],p[i]=s[i]+i;    dui[t=w=1]=0;    for (int i=1; i<=n; ++i){        while (t<w&&calc(dui[t+1],dui[t])<=p[i]) ++t;        int k=dui[t];        f[i]=f[k]+(p[i]-p[k]-m)*(p[i]-p[k]-m);        while (t<w&&calc(i,dui[w])<calc(dui[w],dui[w-1])) --w;        dui[++w]=i;    }    PRintf("%lld",f[n]);    return 0;}寫在最后：雖說這題是斜率優化的入門題，但是要真正弄明白也是不容易的。希望讀者們能多加思考，并AC這題。