cogs 1330 [HNOI2008]玩具装箱toy
瞎扯，急忙AC的请跳过
感觉数据结构写的太多了有点晕=+
发现还没学斜率优化+-
于是来学一学QwQ
上次这题打了个决策优化直接水过了。。理论O(n^2)
蒯个链接
来推一推～
设f[i]为搞定区间1~i的答案。
推出转移方程：
[f[i]=min(f[j]+(s_i-s_j+i-j-1-L)^2) (jin[0,i-1])
]
其中(s_i)为(sum_{j=1}^{i}C_j)
这里优化一下：(s_i)表示(i+sum_{j=1}^{i}C_j)，转移方程简化为
[f[i]=min(f[j]+(s_i-s_j-1-L)^2) (jin[0,i-1])
]
其实没那个必要优化，只是看着爽
然后，(s_i-1-L)只和(i)有关，(-s_j)只和j有关。一次转移中(i)是不会变的，(s_i-1-L)也是不会变的。
令(X=s_i-1-L).
(f[i]=min(f[j]+(X-s_j)^2))
( =min(f[j]+X^2+s_j^2-2Xs_j))
那个(X^2)与(j)毫无关联，完全可以提出来。
( =min(f[j]+s_j^2-2Xs_j)+X^2)
换一个角度：一个(j)会转移给不同的(i)，转移过程中(f[j]+s_j^2)不会改变，改变的只有(-2Xs_j)
然后，由于(X)的不同，转移过去的值也不同。
这个值其实是个一次函数(y=-2Xs_j+f[j]+s_j^2).
把(-2s_j)看成(k)，把(f[j]+s_j^2)看成(b).
画出笛卡尔平面直角坐标系。
（自行脑补，懒得画了）
有一些线是不需要的，因为x取什么值，它都取不到最小，可以删除
然后维护一个单调队列放所有的线
可以发现(k)单调递减，(x)单调递增，所以很好维护，如果队首答案>队首+1答案直接hd++，懒得证。
怎么维护真的懒得写了。。。下凸壳的左半部分
然后直接上代码吧？
感觉是最详细的一篇博客了
// It is made by XZZ
#include<cstdio>
#include<algorithm>
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define db double
typedef long long ll;
il int gi(){
rg int x=0,f=1;rg char ch=getchar();
while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*f;
}
const int maxn=50001;
ll s[maxn],f[maxn];
struct line{ll k,b;};
struct point{db x,y;};
il point javascript(const line&a,const line&b){
static point ret;
ret.x=(a.b-b.b)/(db)(a.k-b.k);
ret.y=ret.x*a.k+a.b;
return ret;
}
line que[maxn];int hd,tl;
int main(){
int n=gi();ll l=gi();
rep(i,1,n)s[i]=gi()+s[i-1];
rep(i,1,n)s[i]+=i;
f[0]=0;
hd=0,tl=-1;
que[++tl]=(line){0,0};
rep(i,1,n){
static ll x;x=s[i]-l-1;
while((tl^hd)&&que[hd].k*x+que[hd].b>que[hd+1].k*x+que[hd+1].b)++hd;
f[i]=que[hd].k*x+que[hd].b+x*x;
static line ls;ls=(line){-2*s[i],f[i]+s[i]*s[i]};
while((tl^hd)&&javascript(ls,que[tl]).x>javascript(ls,que[tl-1]).x)--tl;
que[++tl]=ls;
}
printf("%lld
",f[n]);
return 0;
}