bzoj1010[HNOI2008]玩具装箱toy

题意：

n个东西，每个有一个长度Ci。要将这些东西分成几段，每段中东西编号连续。东西编号从i到j的段长度为x=i-j+sigma(k,i,j)Ck,费用为(x-L)^2（L为常量），求最小费用。n≤50000

题解：

裸斜率优化dp：f[i]=f[j]+((i-j-1)+sum[i]-sum[j]-L)^2，j比k好当且仅当(f[j]-f[k]+(j+sum[j])^2-(k+sum[k])^2)/(j+sum[j]-k-sum[k])>2*(i+sum[i]-L-1)。注意longlong。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #define inc(i,j,k) for(int i=j;i<=k;i++)
 5 #define maxn 50500
 6 #define ll long long
 7 using namespace std;
 8 
 9 inline int read(){
10     char ch=getchar(); int f=1,x=0;
11     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
12     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
13     return f*x;
14 }
15 int n,l,r,q[maxn]; ll L,sum[maxn],f[maxn];
16 ll sqr(ll x){return x*x;}
17 double calc(int j,int k){
18     return (double)(f[j]-f[k]+sqr(j+sum[j])-sqr(k+sum[k]))/(double)(j+sum[j]-k-sum[k]);
19 }
20 int main(){
21     n=read(); L=(ll)read(); inc(i,1,n){ll a=(ll)read(); sum[i]=sum[i-1]+a;} l=r=1;
22     inc(i,1,n){
23         while(l<r&&calc(q[l],q[l+1])<2*(i+sum[i]-L-1))l++;
24         f[i]=f[q[l]]+sqr((ll)(i-q[l]-1)+sum[i]-sum[q[l]]-L);
25         while(l<r&&calc(q[r-1],q[r])>calc(q[r],i))r--; q[++r]=i;
26     }
27     printf("%lld",f[n]); return 0;
28 }

20160613