1 #include
     
       2 #include
      
        3 #define M 50005 4 using namespace std; 5 long long sum[M],f[M],n,L,q[M],h,t,C; 6 double gg(int x,int y) 7 { 8    return(f[y]-f[x]+(sum[y]+C)*(sum[y]+C)-(sum[x]+C)*(sum[x]+C))/(2.0*(sum[y]-sum[x])); 9 }10 int main()11 {12     scanf("%d%d",&n,&L);13     C=L+1;14     for(int i=1;i<=n;i++)15       {16         int a1;17         scanf("%d",&a1);18         sum[i]=sum[i-1]+a1;19       }20     for(int i=1;i<=n;i++)21       sum[i]+=i;22     h=1;23     t=1;24     q[1]=0;25     for(int i=1;i<=n;i++)26       {27         for(;h
       
      
     

这是个斜率优化dp，f[i]=f[j]+(sum[i]-sum[j]+i-j+1-L)^2;

sum数组为前缀和，让sum[i]+=i;C=L-1;

所以f[i]=f[j]+(sum[i]-sum[j]-C)^2;

如果从f[j]转移比从f[k]转移优

即 f[j]+(sum[i]-sum[j]-C)^2<f[k]+(sum[i]-sum[k]-C)^2

化简得  (f[j]-f[k]+(sum[j]+C)*(sum[j]+C)-(sum[k]+C)*(sum[k]+C))/(2*(sum[j]-sum[k]))<sum[i]

这样斜率优化就出去了。