题意
你可以将一段连续的玩具扔到同一个容器中，如果要将 $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)$ 考虑优化。
优化1
设$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)$ 预计得分：20pt
优化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$。 那么就斜率优化鸭。 
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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;
}
|