BZOJ 1010

若将第$j+1$件到第$i$件放在一起，则总共(算上之前的决策)需要花费$f_i=f_j+(\sum_{k=j+1}^{i}C_k+i-j-L-1)^2$

所以方程为$f_i=min{\lbrace}f_j+(sum_i-sum_j+i-j-L-1)^2\rbrace\ (sum_x=\sum_{i=1}^{x}C_i)$

若决策$k$优于决策$j(0{\leq}k,j<i)$，则$f_k+(sum_i+i-sum_k-k-L-1)^2<f_j+(sum_i+i-sum_j-j-L-1)^2$

整理一下，设$P_i=sum_i+i$，把含$i$的都扔到一边，得$f_k+(P_k+L+1)^2-f_j-(P_j+L+1)^2<P_i(P_k-P_j)$

把$(P_k-P_j)$除过去，得到了一个类似计算斜率的式子，设$G_i=f_i+(P_i+L+1)^2$，得到$\frac{G_k-G_j}{P_k-P_j}<P_i$

因为$P_i$单调递增，所以斜率单调递增，成了下凸壳，用单调队列搞一下就行了

对于每次决策$f_i$，由上面的公式可知，最优解就在下凸壳上最后一个满足斜率小于$P_i$的线段的右端点

所以对于每次决策，在单调队列中找到最优解，更新$f_i$，维护下凸壳性质并加入当前点就好了

注意int64

program bzoj_1010;
var q:array[0..50000]of longint;
    n,i,l,hd,tl:longint;
    f,pre:array[0..50000]of int64;
 
function calc(i,j:longint):extended;
begin
  exit((f[i]-f[j]+sqr(pre[i]+l+1)-sqr(pre[j]+l+1))/((pre[i]-pre[j])*2));
end;
 
begin
  readln(n,l);
  for i:=1 to n do
  begin
    read(pre[i]);
    inc(pre[i],pre[i-1]);
  end;
  for i:=1 to n do inc(pre[i],i);
  hd:=0;
  tl:=0;
  for i:=1 to n do
  begin
    while (hd<tl)and(calc(q[hd],q[hd+1])<pre[i]) do inc(hd);
    f[i]:=f[q[hd]]+sqr(pre[i]-pre[q[hd]]-l-1);
    while (tl>hd)and(calc(q[tl-1],q[tl])>calc(q[tl],i)) do dec(tl);
    inc(tl);
    q[tl]:=i;
  end;
  writeln(f[n]);
end.