设\(S_i=\sum_{i=1}^n C_i\)

易得\(n^2\)方程

设\(f[i]\)为处理前\(i\)个玩具的最小费用

\(f_i=min(f_j+(i-j+s_i-s_j-L)^2)(j<i)\)

\(f_i=f_j+(i-j+s_i-s_j-L-1)^2\)

设\(a_i=s_i+i,b_j=-s_j-j-L-1\)

\(f_i=f_j+a_i^2+2a_ib_j+b_j^2\)

将\(i\),\(j\)相关的放到一起

\(f_i-a_i^2-2a_ib_j=f_j+b_j^2\)

设\(b_j=x,f_j+b_j^2=y,f_i-a_i^2=b\)

则变为一条直线\(-2a_ix+b=y\)

我们实际上要找的答案\(f_i\)就是最小化一个斜率为\(-2a_i\)的直线过点\((x,y)\)在\(y\)轴上的截距\(b\)加上定值\(a_i^2\)

因为\(-2a_i\)递减,用单调队列维护一个上凸包就可以了。

/*@Date    : 2019-07-31 10:46:24@Author  : Adscn (adscn@qq.com)@Link    : https://www.cnblogs.com/LLCSBlog*/#include
    
     using namespace std;#define IL inline#define RG register#define gi getint()#define gc getchar()#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)IL int getint(){    RG int xi=0;    RG char ch=gc;    bool f=0;    while(ch<'0'||ch>'9')ch=='-'?f=1:f,ch=gc;    while(ch>='0'&&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;    return f?-xi:xi;}template
     
      IL void pi(T k,char ch=0){    if(k<0)k=-k,putchar('-');    if(k>=10)pi(k/10,0);    putchar(k%10+'0');    if(ch)putchar(ch);}#define int long longconst int N=1e6;int s[N];int f[N];int n,L;inline int A(int i){return s[i]+i;}inline int B(int i){return -s[i]-i-L-1;}inline int sqr(int i){return i*i;}inline double slope(int i,int j){return (double)(f[i]+sqr(B(i))-f[j]-sqr(B(j)))/(B(i)-B(j));}signed main(void){    n=gi,L=gi;    for(int i=1;i<=n;++i)s[i]=s[i-1]+gi;    static int Q[N*2];    int l=0,r=-1;    Q[++r]=0;    for(int i=1;i<=n;++i)    {        while(l
      
       =-2*A(i))++l;        f[i]=f[Q[l]]+sqr(A(i)+B(Q[l]));    //  assert(slope(1,2)==slope(2,1));        while(l
       
        <=slope(Q[r-1],i))--r;        Q[++r]=i;    }    cout<
        
         <