Description

　　P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压

缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过

压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容

器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一

个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，

如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容

器，甚至超过L。但他希望费用最小.

Input

　　第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7

Output

　　输出最小费用

Sample Input

5 4

3

4

2

1

4

Sample Output

1

HINT

Source

 

然而弱渣还是不会斜率优化。。。

跟诗人小G一模一样。。。

这题是可以用last轻松水过的。。。

做这个题只是纯粹为了练一练二分栈的板子，具体题解见诗人小G。

下面有斜率优化版。。。初学者可以参考

1 // MADE BY QT666 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 #include
             
              11 #include
              
               12 #define lson num<<113 #define rson num<<1|114 #define int long long15 using namespace std;16 typedef long long ll;17 const int N=100050;18 int gi()19 {20 int x=0,flag=1;21 char ch=getchar();22 while(ch<'0'||ch>'9'){ if(ch=='-') flag=-1;ch=getchar();}23 while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();24 return x*flag;25 }26 struct data{ int l,r, p;}q[N];27 int a[N],f[N];28 int n,L;29 int cal(int j,int i){30 return f[j]+(i-j-1+a[i]-a[j]-L)*(i-j-1+a[i]-a[j]-L);31 }32 int find(data t,int x){33 int l=t.l,r=t.r;34 while(l<=r){35 int mid=(l+r)>>1;36 if(cal(t.p,mid)
               
                q[head].r)head++;50 f[i]=cal(q[head].p,i);51 if(head>tail||cal(i,n)<=cal(q[tail].p,n)){52 while(head<=tail&&cal(i,q[tail].l)<=cal(q[tail].p,q[tail].l))53 tail--;54 if(head>tail)55 q[++tail]=(data){i,n,i};56 else{57 int t=find(q[tail],i);58 q[tail].r=t-1;59 q[++tail]=(data){t,n,i};60 }61 }62 }63 printf("%lld",f[n]);64 }
               
              
             
            
           
          
         
        
       
      
     

 蒟蒻终于get了斜率优化。。。

推斜率方程：

f[j]+(s[i]-s[j]-L)^2<=f[k]+(s[i]-s[k]-L)^2;

展开

f[j]+(s[j]+L)^2-2*s[i]*(s[j]+L)+s[i]^2<=f[k]+(s[k]+L)^2-2*s[i]*(s[k]+L)+s[i]^2;

消掉两边相同的

f[j]+(s[j]+L)^2-2*s[i]*s[j]<=f[k]+(s[k]+L)^2-2*s[i]*s[k];

发现f[j]+(s[j]+L)^2只跟j有关

我们用换元：

令y(j)=f[j]+(s[j]+L)^2;

有两个相乘的,我们把系数2*s[i]看做一个斜率K;

再令x(j)=s[j];

那么原不等式化为:

y(j)-K*x(j)<=y(k)-K*x(k);

移项后得到：

K*(x(k)-x(j))<=y(k)-y(j);

1.当x(k)>x(j)时,K<=(y(k)-y(j))/(x(k)-x(j));

2.当x(k)<x(j)时,K>=(y(k)-y(j))/(x(k)-x(j));

然后玄学的力量就引导我们用一个单调队列维护凸包。。。

代码附上：

真正的线的神教在最下面(千万不要错过)：

1 // MADE BY QT666 2 #include
     
       3 #include
      
        4 #include
       
         5 #include
        
          6 #include
         
           7 #include
          
            8 #include
           
             9 #include
            
             10 #include
             
              11 #include
              
               12 #define lson num<<113 #define rson num<<1|114 #define int long long15 using namespace std;16 typedef long long ll;17 const int N=100050;18 int gi()19 {20 int x=0,flag=1;21 char ch=getchar();22 while(ch<'0'||ch>'9'){ if(ch=='-') flag=-1;ch=getchar();}23 while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();24 return x*flag;25 }26 int sum[N],f[N],q[N],L;27 int Y(int x){28 return f[x]+(sum[x]+L)*(sum[x]+L);29 }30 int X(int x){31 return sum[x];32 }33 double cal(int j,int k){34 return (Y(k)-Y(j))/(2.0*(X(k)-X(j)));35 }36 main()37 {38 int n=gi();L=gi();L++;39 for(int i=1;i<=n;i++) sum[i]=gi()+sum[i-1];40 for(int i=1;i<=n;i++) sum[i]+=i;41 int head=1,tail=0;q[++tail]=0;42 for(int i=1;i<=n;i++){43 while(head
               
                <=sum[i]) head++;44 int t=q[head];45 f[i]=f[t]+(sum[i]-sum[t]-L)*(sum[i]-sum[t]-L);46 while(head
                
               
              
             
            
           
          
         
        
       
      
     

 方程：

f[j]+(a[i]-a[j]-L)^2;

展开

f[j]+a[i]^2-2*a[i]*(a[j]+L)+(a[j]+L)^2;

整理

f[j]+a[j]^2+2*a[j]*L-2*a[i]*a[j]+a[i]*a[i]-2*a[i]*L;

利用线的套路：

b=f[j]+a[j]^2+2*a[j]*L,k=-2*a[j],x=a[i],常数为：a[i]*a[i]-2*a[i]*L;

简短有力，附上代码：

// MADE BY QT666#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #define lson num<<1#define rson num<<1|1#define int long longusing namespace std;typedef long long ll;const int N=100050;int gi(){ int x=0,flag=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') flag=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*flag;}struct data{int k,x,b;}g[N],q[N];int n,L,f[N],a[N];main(){ n=gi(),L=gi();L++; for(int i=1;i<=n;i++) a[i]=gi()+a[i-1]; for(int i=1;i<=n;i++) a[i]+=i,g[i].k=-2*a[i],g[i].x=a[i]; int head=1,tail=1; for(int i=1;i<=n;i++){ while(head
               
                =q[head+1].k*g[i].x+q[head+1].b) head++; f[i]=q[head].k*g[i].x+q[head].b+a[i]*a[i]-2*a[i]*L+L*L; g[i].b=f[i]+a[i]*a[i]+2*a[i]*L; while(head
                
                 <=(q[tail].b-q[tail-1].b)*(q[tail].k-g[i].k)) tail--; q[++tail]=g[i]; } printf("%lld",f[n]);}