题目传送门(BZOJ)
>原文链接<

题解 :

状态 :

$F[i]$代表已经从$1$装到$i$的最小花费

转移 :

$F[i] = \min{F[j]+(s[i]-s[j]+i-j-L)^2}$其中$s$是$c$的前缀和.

为了方便优化, 我们让$s$变成$c[i]+1$的前缀和, 式子变成

$F[i] = \min{F[j]+(s[i]-s[j]-L-1)^2}$, 我们再令$L = L+1$

就变成了$F[i] = \min{F[j]+(s[i]-s[j]-L)^2}$

看上去有点麻烦, 展开整理得 :

$F[i]-s[i]^2+2\times L\times s[i]=-2\times s[i]\times s[j]+f[j]+s[j]^2+L^2+2\times s[j]\times L$

$k = -2\times s[j]$

$b = f[j]+s[j]^2+L^2+2\times s[j]\times L$

$x = s[i]$

转移时

$F[i] = K_j\times x + b + 2\times s[i]^2-2\times L \times s[i]$

$j$通过斜率优化得到即可

注意开long long

代码 :

#include <cstdio>#include <iostream>#include <cstring>#include <algorithm>#define int long longusing namespace std;#define K(j) (-2*s[j])#define B(j) (f[j]+s[j]*s[j]+L*L+2*s[j]*L)#define Y(i, j) (K(j)*s[i]+B(j))int q[60000], l, r;int x, L, n, s[51000], f[51000];inline bool cmp(int i, int j, int k) { int x = (K(i)-K(j))*(B(k)-B(i)); int y = (K(i)-K(k))*(B(j)-B(i)); return x>=y;}#undef intint main() { scanf("%lld%lld", &n, &L); L++; for(int i = 1; i <= n; i ++ ) { scanf("%lld", &x); s[i] = s[i-1]+x+1; } for(int i = 1; i <= n; i ++ ) { while(l<r&&Y(i, q[l])>Y(i, q[l+1]))l++; f[i] = Y(i, q[l])+s[i]*s[i]-2*L*s[i]; while(l<r&&cmp(i, q[r], q[r-1]))r--; q[++r] = i; } printf("%lld\n", f[n]);}