你可以将一段连续的玩具扔到同一个容器中,如果要将 i 号玩具到 j 号玩具 (i\le j) 放到同一个容器中,则容器长度不小于 x=j-i+ \displaystyle\sum_{k=i}^{j}C_k制作容器的费用与容器的长度有关,根据教授研究,如果容器长度为 x,其制作费用为 (X-L)^2,其中 L 是一个常量。 求最小花费。 对于全部数据,1\le N\le 5\times 10^4,1\le L,C_i\le 10^7。
首先,考虑dp。 设f[i]表示前i个玩具的最小花费,那么最终的答案就是f[n]。 那么很容易就可以得知:f[i]=min(f[j]+(i-j+\sum_{k=i}^{j}C_k-L-1)^2)(1\leq j <i,1\leq i\leq n)
设sum[i]表示C数组的前缀和,那么转移方程可化为:f[i]=min(f[j]+(i-j-sum[j]+sum[i]-L-1)^2)(1<=i<=n,1<=j<i)O(N^3)–>O(N^2)
考虑斜率优化。 原转移方程可化为:f[i]=f[j]+(i+sum[i]-L-1-sum[j]-j)^2 设A[i]=sum[i]+i,B[i]=sum[i]+i-L-1 则f[i]=f[j]+(A[i]-B[j])^2, f[i]=f[j]+A[i]^2+B[j]^2-2\times A[i]\times B[j], 2\times A[i]\times B[j]+f[i]-A[i]^2=f[j]+B[j]^2。 设x=B[j],y=f[j]+B[j]^2, 那么y=x\times (2\times A[i])+(f[i]-A[i]^2),slope=2\times A[i]。 f[i]=y+A[i]^2-2\times A[i]\times x。 那么就斜率优化鸭。
#include<bits/stdc++.h>
#define int long long
#define sqrs(x) ((x)*(x))
#define A(i) ((sum[i])+(i))
#define B(i) ((sum[i])+(i)+(L)+(1))
#define X(j) (B(j))
#define Y(j) ((f[j])+sqrs(B(j)))
#define slope(i,j) (double)((double)(Y(i)-Y(j))/(double)(X(i)-X(j)))
#define Slope(i) (2*(A(i)))
#define solve(i,j) (f[j]+sqrs(i-j-sum[j]+sum[i]-L-1))
using namespace std;
inline int read(){
int ret=0,f=1;char ch=getchar();
while (ch<'0'ch>'9') {if (ch=='-') f=-f;ch=getchar();}
while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
return ret*f;
}
inline void write(int zx){
if(zx<0) putchar('-'),zx=-zx;
if(zx<10) putchar(zx+'0');
else{
write(zx/10);
putchar(zx%10+'0');
}
}
int n,L,sum[50010],f[50010],q[50010],h,t;
signed main(){
n=read();L=read();
for(int i=1;i<=n;i++) sum[i]=sum[i-1]+read();
memset(f,63,sizeof(f));
f[0]=0;h=t=1;
for(int i=1;i<=n;i++){
while(h<t&&slope(q[h],q[h+1])<Slope(i)) h++;
f[i]=f[q[h]]+sqrs(A(i)-B(q[h]));
while(h<t&&slope(q[t-1],q[t])>slope(i,q[t-1])) t--;
q[++t]=i;
}
write(f[n]);putchar('\n');
return 0;
}