Description
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过L。但他希望费用最小.
Input
第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
Output
输出最小费用
Sample Input
5 4
3
4
2
1
4
Sample Output
1
题目分析：
首先很容易写出DP方程 令f[i]是将前i件物品放入容器的最小价值 sum[i]是c[i]的前缀和
f[i]=min{ f[j]+(i-(j+1)+sum[i]-sum[j]-L)^2 } (1<=j<i) ;
经过整理：
f[j]+(sum[j]+j+(L+1))^2=2*sum[i]*(sum[j]+(L+1))+f[i]-(sum[i]+i)^2
将sum[i]+i，L++，得到
f[j]+(sum[j]+L)^2=2*sum[i]*(sum[j]+L)+f[i]-sum[i]^2
令y=f[j]+(sum[j]+L)^2，k=2*sum[i]，x=(sum[j]+L)，b=f[i]-sum[i]^2
直接化成了y=kx+b 可以进行斜率优化
最后 切记：l=r=0 因为 可以从0转移过来
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n;
long long L,c[60000],sum[60000],f[60000];
long long calc(long long x) { return x*x; }
long long yi(int i) { return f[i]+calc(sum[i]+L); }
long long xi(int i) { return sum[i]; }
int q[60000];
int l,r;
int main()
{
scanf("%d%lld",&n,&L);
for(int i=1;i<=n;i++)
scanf("%lld",&c[i]),sum[i]=sum[i-1]+c[i];
for(int i=1;i<=n;i++) sum[i]+=i;
L++;
for(int i=1;i<=n;i++)
{
while(l<r&& yi(q[l+1])-yi(q[l])<(sum[i]<<1)*(xi(q[l+1])-xi(q[l])) )l++;
f[i]=f[q[l]]+calc(sum[i]-sum[q[l]]-L);
while(l<r&& (yi(i)-yi(q[r]))*(xi(q[r])-xi(q[r-1]))<(yi(q[r])-yi(q[r-1]))*(xi(i)-xi(q[r]))) r--;
q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}
