1010: [HNOI2008]玩具装箱toy
题目：传送门
题解：
很明显的一题动态规划...
f[i]表示1~i的最小花费
那么方程也是显而易见的：f[i]=min(f[j]+(sum[i]-sum[j]+i-(j+1)-L)^2) (j<i)
但是这样的方程写下来要n^2....50000*50000...GG
所以我们要用斜率优化这个神器！！！
设s[i]=sum[i]+i,L+=1;
那么就开始推吧：
f[i]=min(f[i],f[j]+(sum[i]-sum[j]+i-j-1-L)^2)
f[i]=min(f[i],f[j]+(s[i]-s[j]-L)^2)
f[j2]+(s[i]-s[j2]-L)^2<=f[j1]+(s[i]-s[j1]-L)^2
f[j2]+(s[i]-L)^2-2*s[j2]*(s[i]-L)+s[j2]^2<=f[j1]+(s[i]-L)^2-2*s[j1]*(s[i]-L)+s[j1]^2
f[j2]+s[j2]^2-2*s[j2]*(s[i]-L)<=f[j1]+s[j1]^2-2*s[j1]*(s[i]-L)
f[j2]-f[j1]+s[j2]^2-s[j1]^2<=2*s[j2]*(s[i]-L)-2*s[j1]*(s[i]-L)
f[j2]-f[j1]+s[j2]^2-s[j1]^2<=2*s[j2]*(s[i]-L)-2*s[j1]*(s[i]-L)
(f[j2]-f[j1]+s[j2]^2-s[j1]^2)/(s[j2]-s[j1])<=2*(s[i]-L)
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
LL L,sum[],s[],f[],list[];
int n;
/*
f[i]=min(f[i],f[j]+(sum[i]-sum[j]+i-j-1-L)^2)
f[i]=min(f[i],f[j]+(s[i]-s[j]-L)^2)
f[j2]+(s[i]-s[j2]-L)^2<=f[j1]+(s[i]-s[j1]-L)^2
f[j2]+(s[i]-L)^2-2*s[j2]*(s[i]-L)+s[j2]^2<=f[j1]+(s[i]-L)^2-2*s[j1]*(s[i]-L)+s[j1]^2
f[j2]+s[j2]^2-2*s[j2]*(s[i]-L)<=f[j1]+s[j1]^2-2*s[j1]*(s[i]-L)
f[j2]-f[j1]+s[j2]^2-s[j1]^2<=2*s[j2]*(s[i]-L)-2*s[j1]*(s[i]-L)
f[j2]-f[j1]+s[j2]^2-s[j1]^2<=2*s[j2]*(s[i]-L)-2*s[j1]*(s[i]-L)
(f[j2]-f[j1]+s[j2]^2-s[j1]^2)/(s[j2]-s[j1])<=2*(s[i]-L)
*/
double slope(int j1,int j2)
{
return (f[j2]-f[j1]+s[j2]*s[j2]-s[j1]*s[j1])/(s[j2]-s[j1]);
}
int main()
{
memset(f,,sizeof(f));
scanf("%d%lld",&n,&L);sum[]=;
LL x;for(int i=;i<=n;i++){scanf("%lld",&x);sum[i]=sum[i-]+x;}
for(int i=;i<=n;i++)s[i]=sum[i]+i;
L++;
int head=,tail=;list[]=;
for(int i=;i<=n;i++)
{
while(head<tail && slope(list[head],list[head+])<=2.0*double(s[i]-L))head++;
int j=list[head];
f[i]=f[j]+(s[i]-s[j]-L)*(s[i]-s[j]-L);
while(head<tail && slope(list[tail],i)<slope(list[tail-],list[tail]))tail--;
list[++tail]=i;
}
printf("%lld\n",f[n]);
return ;
}