(\)
Description
现有编号为 (1sim N) 的 (N) 件玩具，第 (i) 件长度为 (C_i) 。
现在要把按顺序排好的玩具划分成若干段，$[l,r] $的长度是 (len_{ lsim r}=r-l+sum_{i=l}^r C_i) 。
一段的代价为 ((len-L)^2) ，其中 (L) 是给出的常量。
求最小总代价。
- (Nle 5 imes10^4,C_i,Lle 10^9)
(\)
Solution
设 (len(l,r)) 表示区间 ((l,r]) 新成一段的最后长度。
显然有 (len(l,r)=r-l-1+sum_{i=l+1}^rC_i)
记录 (sum[i]=sum_{j=1}^iC_j) ，那么有
发现式子可以表示成 (l,r) 相关，我们设 (t(i)=i+sum[i]) ，那么有
我们设 (w(l,r)) 表示区间 ((l,r]) 新生成一段的代价，那么有
不妨再设 (g(i)=t(i)+1+L) ，那么有 (w(l,r)=igg(t(r)-g(l)igg)^2=t(r)^2+g(l)^2-2g(l)t(r))
显然 (t) 和 (g) 是可以 (O(n)) 预处理的，询问可以做到 (O(1)) 。
(\)
设 (f[i]) 表示到第 (i) 个玩具为止 (() 含第 (i) 个 ())，全部装箱的最小代价。
假设我们现在找到了最优转移点 (j) ，那么有
移项，有
此时我们可以将转移模型抽象到二维平面了，设点 ((g(j),f[j]+g(j)^2)) 表示一个状态 。
我们将 (2t(i)) 看作斜率，将 (f[i]-t(i)^2) 看作与 (y) 轴相交点的纵坐标。
目标明确了：选择之前在坐标系上的任意一点用斜率构建直线，使得这一纵坐标最小。
(\)
因为 (C_ige 1) 所以 (t(i)ge 0) ，我们的答案显然只会产生在下凸壳上。
如果我们用 (j) 去刻画 (f[j]) 对应的状态，考虑对于一个状态 (i) 的更新，(j) 点的答案合适劣于 (k) 点的答案。
移项，把 (j,k) 的答案都带进去，列出不等式，化简，可以得到 (() 博主太懒 ():)
继续分析，还是因为 (C_ige 1) ，所以 (t(i)) 是单调不降的。
因此注意到不等式右侧是单调不降的，所以每一个位置的最优决策点 (j) 单调不减。
用队列维护点，队头用单调队列那一套就可以搞了。
关于下凸包的维护，可以考虑队尾是一个单调栈，每次按照斜率逐个弹栈就可以了。
(\)
特别提醒：此做法中 (g(0)) 初值不为 (0) ，而转移要用到，在开始的时候记得设 (g(0)=1+L) 。
其实设 (g(i)=i+m,t(i)=g(i)-1-L) ，可以惊喜的发现，后面所有的式子都是不变的。
而且也不需要预处理初值，因为转移方程在没有 (t(j)) 这一项，而在这一设法中， (g(0)=0) 。
(\)
Code
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 50010
#define R register
#define gc getchar
using namespace std;
typedef long long ll;
inline ll rd(){
ll x=0; bool f=0; char c=gc();
while(!isdigit(c)){if(c=='-')f=1;c=gc();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=gc();}
return f?-x:x;
}
ll n,m,t[N],g[N],f[N],q[N],hd,tl;
inline ll w(ll x,ll k){
return f[x]+k*k+g[x]*g[x]-2*k*g[x];
}
inline double calck(ll x,ll y){
return (double)(f[x]+g[x]*g[x]-f[y]-g[y]*g[y])/(double)(g[x]-g[y]);
}
int main(){
n=rd(); m=rd();
for(R int i=1,sum=0;i<=n;++i){
sum+=rd();
t[i]=i+sum; g[i]=t[i]+1+m;
}
q[hd=tl=1]=0;
g[0]=1+m;
for(R int i=1;i<=n;++i){
while(hd<tl&&calck(q[hd+1],q[hd])<(double)t[i]*2) ++hd;
f[i]=w(q[hd],t[i]);
while(hd<tl&&calck(q[tl],q[tl-1])>calck(i,q[tl])) --tl;
q[++tl]=i;
}
printf("%lld
",f[n]);
return 0;
}