BZOJ 1010

若将第$j+1$件到第$i$件放在一起,则总共(算上之前的决策)需要花费$f_i=f_j+(\sum_{k=j+1}^{i}C_k+i-j-L-1)^2$

所以方程为$f_i=min{\lbrace}f_j+(sum_i-sum_j+i-j-L-1)^2\rbrace\ (sum_x=\sum_{i=1}^{x}C_i)$

若决策$k$优于决策$j(0{\leq}k,j<i)$,则$f_k+(sum_i+i-sum_k-k-L-1)^2<f_j+(sum_i+i-sum_j-j-L-1)^2$

整理一下,设$P_i=sum_i+i$,把含$i$的都扔到一边,得$f_k+(P_k+L+1)^2-f_j-(P_j+L+1)^2<P_i(P_k-P_j)$

把$(P_k-P_j)$除过去,得到了一个类似计算斜率的式子,设$G_i=f_i+(P_i+L+1)^2$,得到$\frac{G_k-G_j}{P_k-P_j}<P_i$

因为$P_i$单调递增,所以斜率单调递增,成了下凸壳,用单调队列搞一下就行了

对于每次决策$f_i$,由上面的公式可知,最优解就在下凸壳上最后一个满足斜率小于$P_i$的线段的右端点

所以对于每次决策,在单调队列中找到最优解,更新$f_i$,维护下凸壳性质并加入当前点就好了

注意int64

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
program bzoj_1010;
var q:array[0..50000]of longint;
n,i,l,hd,tl:longint;
f,pre:array[0..50000]of int64;
function calc(i,j:longint):extended;
begin
exit((f[i]-f[j]+sqr(pre[i]+l+1)-sqr(pre[j]+l+1))/((pre[i]-pre[j])*2));
end;
begin
readln(n,l);
for i:=1 to n do
begin
read(pre[i]);
inc(pre[i],pre[i-1]);
end;
for i:=1 to n do inc(pre[i],i);
hd:=0;
tl:=0;
for i:=1 to n do
begin
while (hd<tl)and(calc(q[hd],q[hd+1])<pre[i]) do inc(hd);
f[i]:=f[q[hd]]+sqr(pre[i]-pre[q[hd]]-l-1);
while (tl>hd)and(calc(q[tl-1],q[tl])>calc(q[tl],i)) do dec(tl);
inc(tl);
q[tl]:=i;
end;
writeln(f[n]);
end.