bzoj1010: [HNOI2008]玩具装箱toy（DP+斜率优化）

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)/(s[j2]-s[j1])<=2*(s[i]-L)

代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 typedef long long LL;
 8 LL L,sum[51000],s[51000],f[51000],list[51000];
 9 int n;
10 /*
11     f[i]=min(f[i],f[j]+(sum[i]-sum[j]+i-j-1-L)^2)
12     f[i]=min(f[i],f[j]+(s[i]-s[j]-L)^2)
13     f[j2]+(s[i]-s[j2]-L)^2<=f[j1]+(s[i]-s[j1]-L)^2
14     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
15     f[j2]+s[j2]^2-2*s[j2]*(s[i]-L)<=f[j1]+s[j1]^2-2*s[j1]*(s[i]-L)
16     f[j2]-f[j1]+s[j2]^2-s[j1]^2<=2*s[j2]*(s[i]-L)-2*s[j1]*(s[i]-L)
17     f[j2]-f[j1]+s[j2]^2-s[j1]^2<=2*s[j2]*(s[i]-L)-2*s[j1]*(s[i]-L)
18     (f[j2]-f[j1]+s[j2]^2-s[j1]^2)/(s[j2]-s[j1])<=2*(s[i]-L)
19 */
20 double slope(int j1,int j2)
21 {
22     return (f[j2]-f[j1]+s[j2]*s[j2]-s[j1]*s[j1])/(s[j2]-s[j1]);
23 }
24 int main()
25 {
26     memset(f,0,sizeof(f));
27     scanf("%d%lld",&n,&L);sum[0]=0;
28     LL x;for(int i=1;i<=n;i++){scanf("%lld",&x);sum[i]=sum[i-1]+x;}
29     for(int i=1;i<=n;i++)s[i]=sum[i]+i;
30     L++;
31     int head=1,tail=1;list[1]=0;
32     for(int i=1;i<=n;i++)
33     {
34         while(head<tail && slope(list[head],list[head+1])<=2.0*double(s[i]-L))head++;
35         int j=list[head];
36         f[i]=f[j]+(s[i]-s[j]-L)*(s[i]-s[j]-L);
37         while(head<tail && slope(list[tail],i)<slope(list[tail-1],list[tail]))tail--;
38         list[++tail]=i;
39     }
40     printf("%lld
",f[n]);
41     return 0;
42 }
43