P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P 教授有编号为
$1⋯n$ 的$n$ 件玩具，第 iii 件玩具经过压缩后的一维长度为$C_i$ 。为了方便整理，P教授要求：
- 在一个一维容器中的玩具编号是连续的。
- 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第
$i$ 件玩具到第$j$ 个玩具放到一个容器中，那么容器的长度将为$x=j−i+\sum\limits_{k=i}^j {C_k}$ 。制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为
$x$ ，其制作费用为$(x-L)^2$ 。其中$L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过$L$ 。但他希望所有容器的总费用最小。第一行有两个整数，用一个空格隔开，分别代表
$n$ 和$L$ 。第
$2$ 到 第$(n + 1)$ 行，每行一个整数，第$(i + 1)$ 行的整数代表第$i$ 件玩具的长度$C_i$ 。输出一行一个整数，代表所有容器的总费用最小是多少。
-
Means : DP + 斜率优化
由于装箱必须符合序号连续，可以得到原转移方程： $$ Let\ pre_i=\sum_{j=1}^iC_i \ f_i=\max\limits_{0\leq j<i}{f_j+(pre_i-pre_j+i-j-1-L)^2}\ Let\ x_i=pre_i+i,\ L'=L+1\ f_i=\max\limits_{0\leq j<i}{f_j+(x_i-x_j-L')^2}\ f_i-(x_i-L')^2=\max\limits_{0\leq j<i}{f_j+y_jjk_iL'-\ Let\ y_i=f_i+x_i^2,\ k_i=-2(L'-x_i), b_i=f_i-(x_i-L')^2\ b_i=\max\limits_{0\leq j<i}{y_j-k_ix_j}\ 使用先前的各个(x,y)和一个确定k求解b_i\ 即在坐标系中平移斜率为k的直线\ 1.最大b_i一定在(x,y)组成的凸包上——入队时处理\ 2.k总是递增的，而最优解即找到k_i<k<k_j——找到后弹出队尾 $$
-
Code (Rank first 2021-10-15)
#include<stdio.h>
#define ll long long
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2))?EOF:*p1++
int n,l,top,but,q[50001];
ll f[50001],p[50001];
char buf[1<<20],*p1,*p2;
inline int read()
{
register int x=0;
register char c=0;
while((c&0xf0)^0x30)c=getchar();
while((c&0xf0)==0x30)x=(x<<1)+(x<<3)+(c^0x30),c=getchar();
return x;
}
inline ll sq(const ll &x)
{
return x*x;
}
inline ll min(const ll &a,const ll &b)
{
return a>b?b:a;
}
inline ll X(const ll &x)
{
return p[x]+x;
}
inline ll Y(const ll &x)
{
return f[x]+sq(X(x));
}
int main()
{
n=read(),l=read();
for(register int i=1;i<=n;i++)
p[i]=p[i-1]+read();
for(register int i=1;i<=n;++i)
{
const int k=-2*(l+1-X(i));
while(but<top && k*(X(q[but+1])-X(q[but]))
>=Y(q[but+1])-Y(q[but]) )but++;
f[i]=f[q[but]]+sq(X(i)-X(q[but])-l-1);
while(top>but&&(Y(i)-Y(q[top])) * (X(q[top])-X(q[top-1]))
<= (Y(q[top])-Y(q[top-1])) * (X(i)-X(q[top])) )top--;
q[++top]=i;
}
printf("%lld\n",f[n]);
}