Luogu

分析

斜率优化。我的式子可能比较长

设 $dp_i$ 表示前 $i$ 个玩具的最小费用，$sum_i$ 表示 $\sum_{j=1}^ic_j$，容易得到状态转移方程

$$ dp_i=\min_{j=0}^{i-1}\left\{dp_j+(i-j-1+sum_i-sum_j-L)^2\right\} $$

为了方便，我们令 $L$ 加 $1$。

于是

$$ dp_i=\min_{j=0}^{i-1}\left\{dp_j+(i-j+sum_i-sum_j-L)^2\right\} $$

我们把 $\min$ 中的东西大力拆开，并把所有项分为三类：

• 与 $j$ 无关的：$i^2+2isum_i-2iL+sum_i\!^2+L^2-2sum_iL$。
• 只和 $j$ 有关的：$dp_j+j^2+2jsum_j+2jL+sum_j\!^2+2sum_jL$。
• 既和 $i$ 有关又和 $j$ 有关的：$-2(i+sum_i)(j+sum_j)$。（这个是因式分解之后的式子）

令 $y_i=dp_i+i^2+2isum_i+2iL+sum_i\!^2+2sum_iL$，$x_i=(i+sum_i)$，$k_i=2(i+sum_i)$，$pre_i=i^2+2isum_i-2iL+sum_i\!^2+L^2-2sum_iL$，那么状态转移方程改写为

$$ dp_i=pre_i+\min_{j=0}^{i-1}\left\{-k_ix_j+y_j\right\} $$

把每个转移点看做一个点 $(x_j,y_j)$，那么我们相当于要找一个点，使得斜率为 $k_i$ 的经过它的直线的纵截距最小。

可以发现可能满足条件的点一定在下凸壳上，因此我们只需要想办法维护下凸壳就好了。

注意到 $k_i$ 和 $x_j$ 都是单增的，因此用单调队列来维护下凸壳，每次队头即为最优转移点。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,L;
int sum[N],dp[N];
int Q[N],h,t;

inline int X(int i) { return i+sum[i]; }
inline int Y(int i) {
    return dp[i]+i*i+2*i*sum[i]+2*i*L+sum[i]*sum[i]+2*sum[i]*L;
}
inline double slope(int i,int j) {
    return 1.0*(Y(i)-Y(j))/(X(i)-X(j));
}
inline int calc(int i,int j) {
    return dp[j]+(i-j+sum[i]-sum[j]-L)*(i-j+sum[i]-sum[j]-L);
}

signed main() {
    n=read(),L=read()+1;
    for (re int i=1;i<=n;++i) sum[i]=sum[i-1]+read();
    dp[0]=0,Q[h=t=1]=0;
    for (re int i=1;i<=n;++i) {
        while (h<t&&calc(i,Q[h])>=calc(i,Q[h+1])) ++h; // pop_front
        dp[i]=calc(i,Q[h]); // 队头为最优决策点
        while (h<t&&slope(Q[t-1],i)<=slope(Q[t-1],Q[t])) --t; // pop_back
        Q[++t]=i; // push_back
    }
    printf("%lld\n",dp[n]);
    return 0;
}