给定序列 \(C\) ，将原序列拆成几个部分,每个部分 \([i,j]\) 费用为 \(j-i+\sum^{j}_{k=i}C_k\) ，最小化费用。 \(n\leq 5\times 10^4\) 。
定义 \(sum[i]\) 为前 \(i\) 项的前缀和， \(dp[i]\) 为将前 \(i\) 项拆成若干个区间的最小费用。那么有一个朴素的 \(O(n^2)\) 做法，直接枚举 \(j\) ， \(dp[i]=min\{dp[j]+(sum[i]+i-sum[j]-j-L)^2\}\) ， \(dp[n]\) 就是答案。
考虑优化式子，令 \(P[i]=sum[i]+i\) ， \(Q[i]=sum[i]+i+L+1\) ，那么
\[dp[i]=dp[j]+(P[i]-Q[j])^2 \]\[dp[i]=dp[j]+P[i]^2-2\times P[i]\times Q[j]+Q[j]^2 \]\[2\times P[i]\times Q[j]+dp[i]-P[i]^2=dp[j]+Q[j]^2 \]令 \(x=Q[j],y=dp[j]+Q[j]^2\) ，原式变成 \(y=2P[i]x-P[i]^2+dp[i]\) 。
那么 \(b\) 的意义就是 \(P[i]^2+dp[i]\) ，又 \(P[i]=sum[i]+i\) 是定值，所以 \(b\) 尽可能的小，就会使 \(dp[i]\) 小。同时注意到 \(2P[i]\) 一定是单调递增的，那么该直线的斜率一定单增。将每一个 \(C_i\) 都转化成点 \((Q[j],dp[j]+Q[j]^2)\) 。如下图，在下凸包上方的点一定不会是最优的，那么可以提前删除。同时，这与单调队列相似，在之后的点中斜率大的有优势，所以可以记录相邻两点构成直线的斜率，然后像单调队列一样 pop 和 push 即可。
#include<bits/stdc++.h>
using namespace std;
int n,L;
double c[50005];
double sum[50005],dp[50005];
int head,tail,q[50005];
#define a(i) (sum[i]+i)
#define b(i) (a(i)+L+1)
#define X(i) b(i)
#define Y(i) (dp[i]+(b(i)*b(i)))
#define slope(i,j) (Y(i)-Y(j))/(X(i)-X(j))
int main(){
scanf("%d %d",&n,&L);
for(int i=1;i<=n;++i){
scanf("%lf",&c[i]);
sum[i]=c[i]+sum[i-1];
}
head=tail=1;
for(int i=1;i<=n;++i){
while(head<tail && slope(q[head],q[head+1])<2*a(i))
++head;
dp[i]=dp[q[head]]+(a(i)-b(q[head]))*(a(i)-b(q[head]));
while(head<tail && slope(i,q[tail-1])<slope(q[tail-1],q[tail]))
--tail;
q[++tail]=i;
}
printf("%lld\n",(long long)dp[n]);
return 0;
}