题目
题目描述
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。
他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P教授有编号为$1…N$的$N$件玩具，第$i$件玩具经过压缩后变成一维长度为$C_i$.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。
同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，
形式地说如果将第$i$件玩具到第$j$个玩具放到一个容器中，那么容器的长度将为$x=j-i+\sum_{k=i}^{j}C_k$
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为$x$,其制作费用为$(X-L)^2$.其中$L$是一个常量。
P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过$L$。但他希望费用最小.
输入输出格式
输入格式：
第一行输入两个整数N，L.
接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
输出格式：
输出最小费用
输入输出样例
输入样例#1：
5 4
3
4
2
1
4
输出样例#1：
1
题解
首先这题的状态转移方程很好推
$f_i$表示前$i$个玩具最小花费，$sum_i$是玩具大小的前缀和
即有：$f_i=f_j+(sum_i-sum_j+i-j-1-L)^2$
然后这样循环肯定TLE然而有40分我就满足了
我们对上面那个式子进行操作：$f_i=f_j+((sum_i+i)-(sum_j+j)-(L+1))^2$
然后设$w_k=sum_k+k$
则有：$f_i=f_j+(w_i-w_j-(L+1))^2$
然后展开：$f_i=f_j+w_i^2-2\times w_i(w_j-(L+1))+(w_j-(L+1))^2$
$f_i+2\times w_i(w_j-(L+1))=f_j+w_i^2+(w_j-(L+1))^2$
联系$b+k\times x=y$
我们可以把$f_i$看为$b$，$2\times w_i$看为$k$，$w_j-(L+1)$看为$x$，等式右边那一大堆看为$y$
由于我们要搞的为$f_i$，即在y轴上的截距，$f_i$小，斜率$k$肯定也得小
然后我们发现$k$有一个上升趋势，就是越往后$k$应该越大（因为$k=2\times w_i$）
所以我们可以用单调队列维护前面的点
每次计算队列里的点对应的斜率$k$，要求$k<2\times w_i$
用满足条件的点$j$更新$f_i$
然后将$i$加入队列，斜率大于$j$和$i$构成的直线的斜率都弹出，这个就搞完了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<queue>
# define LL long long
using namespace std;
const int MAX=5e4+1;
int n,m,l;
int qu[MAX];
LL sum[MAX],f[MAX];
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
double X(int i)
{
return sum[i];
}
double Y(int i)
{
LL L=sum[i]+l;
return f[i]+L*L;
}
double look(int x,int y)
{
return (Y(x)-Y(y))/(X(x)-X(y));
}
int main()
{
n=read(),l=read()+1;
for(int i=1;i<=n;i++)
sum[i]=read()+sum[i-1];
for(int i=1;i<=n;i++)
sum[i]+=i;
int he=1,ta=1;
for(int i=1;i<=n;i++)
{
int T=(sum[i]<<1);
while(he<ta&&look(qu[he],qu[he+1])<T) ++he;
int tt=qu[he];
LL L=sum[i]-sum[tt]-l;
f[i]=f[tt]+L*L;
while(he<ta&&look(qu[ta-1],qu[ta])>look(qu[ta],i)) --ta;
qu[++ta]=i;
}
printf("%lld",f[n]);
return 0;
}
