动态规划，四边形不等式优化，这道题还可以斜率优化。
CODE:
/*
PROGRAM: $PROGRAM
AUTHOR: Su Jiao
DATE: 2010-5-29
DESCRIPTION:
湖南2008年省选 玩具装箱
*/
#include <stdio.h>
class Application
{
FILE* in;
FILE* out;
static const int MAXN=50000;
int N,L;
int c[MAXN];
void print_long_long_int(long long int number)
{
if (number>=10) print_long_long_int(number/10);
fprintf(out,“%d”,number%10);
}
public:
Application(const char* input=0,const char* output=0)
:in(input?fopen(input,“r”):stdin),
out(output?fopen(output,“w”):stdout)
{
fscanf(in,“%d%d”,&N,&L);
for (int i=0;i<N;i++)
fscanf(in,“%d”,c+i);
}
~Application()
{
fclose(in);
fclose(out);
}
int run()
{
long long int sum[MAXN+1];
sum[0]=0;
for (int i=0;i<N;i++)
sum[i+1]=sum[i]+c[i];
long long int f[MAXN+1];
/*
f[0]=0;
for (int i=1;i<=N;i++)
{
f[i]=1000000000000000000ll;
for (int j=0;j<i;j++)
{
long long int x=i-j-1+sum[i]-sum[j]-L;
x*=x;
if (f[i]>f[j]+x)
f[i]=f[j]+x;
}
}
*/
int head,tail;
int begin[MAXN+1],end[MAXN+1],best[MAXN+1];
f[0]=0;
head=tail=0;
begin[tail]=0;
end[tail]=N;
best[tail]=0;
for (int i=1;i<=N;i++)
{
while (end[head]<i) head++;
int j=best[head];
long long int x=i-j-1+sum[i]-sum[j]-L;
f[i]=f[j]+x*x;
#define value(i,j) \
(f[j]+(i-j-1+sum[i]-sum[j]-L)*(i-j-1+sum[i]-sum[j]-L))
while (head<tail
&&value(begin[tail],best[tail])>=value(begin[tail],i))
end[tail-1]=end[tail],tail–;
int l=begin[tail],r=end[tail]+1;
while (l+1!=r)
{
int mid=(l+r)>>1;
if (value(mid,best[tail])<value(mid,i)) l=mid;
else r=mid;
}
if (l+1<=end[tail])
{
tail++;
begin[tail]=l+1;
end[tail]=end[tail-1];
best[tail]=i;
end[tail-1]=l;
}
}
print_long_long_int(f[N]);
fprintf(out,“\n”);
return 0;
}
};
int main()
{
Application app;
return app.run();
}