日常刷水。。

n<=50000个数，把一段连续的数隔在一起的代价为$(x-L)^2$，其中$x=i-j+\sum_{k=j}^{i} A_k,j<=i$。问最小代价。

一开始看成除法然后浪费了20min（逃

瞎yy一下dp，$f(i)$--前i个数的最小分隔代价，$f(i)=min(f(j)+(s_i-s_j+i-j-1-L)^2)$，其中$s_i$表示前缀和。

令$b_i=s_i+i$，则$f(i)=min(f(j)+(b_i-b_j-(L+1))^2)$。

这是个需要优化的dp，设状态j比k优，则有$f(j)+(b_i-b_j-(L+1))^2<f(k)+(b_i-b_k-(L+1))^2$，平方拆开整理得$(f(j)-f(k)+b_j^2-b_k^2)/(2*(b_j-b_k))<b_i-L-1,j>k$。

右边那东西单增的，就斜率优化，上单调队列咯

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 //#include
          
            6 //#include
           
             7 //#include
            
              8 //#include
             
               9 using namespace std;10 11 int n,L;12 #define maxn 5001113 int a[maxn];14 #define LL long long15 LL f[maxn],b[maxn];16 int que[maxn],head,tail;17 LL sqr(LL x) { return x*x;}18 double calc(int i,int j) { return ((f[i]-f[j])+1.0*b[i]*b[i]-1.0*b[j]*b[j])/(2*(b[i]-b[j]));}19 int main()20 {21 scanf("%d%d",&n,&L);22 for (int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=b[i-1]+a[i];23 for (int i=1;i<=n;i++) b[i]+=i;24 b[0]=0; head=0; tail=1; que[0]=0;25 for (int i=1;i<=n;i++)26 {27 const LL cmp=b[i]-L-1;28 while (head
              
               calc(i,que[tail-1])) tail--;31 que[tail++]=i;32 }33 printf("%lld\n",f[n]);34 return 0;35 }