Description
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有 的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。P教授有编号为1...N的N件玩具，第i件玩具 经过压缩后变成一维长度为Ci.为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。同时如果一个一维容器中有多个玩具，那么两件玩具之间要加 入一个单位长度的填充物，形式地说如果将第i件玩具到第j个玩具放到一个容器中，那么容器的长度将为 x=j-i+Sigma(Ck) i<=K<=j 制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为x,其制作费用为(X-L)^2.其中L是一个常量。P教授不关心容器的数目，他可以制作 出任意长度的容器，甚至超过L。但他希望费用最小.
Input
第一行输入两个整数N，L.接下来N行输入Ci.1<=N<=50000,1<=L,Ci<=10^7
Output
输出最小费用
Sample Input
3
4
2
1
4
Sample Output
分析
这已经是HNOI2008第三道dp了吧……
首先我们还是要写出转移方程：$$f(i) = \min_{0 \leq j < i} \{ f(j) + (S(i) - S(j) - L - 1)^2 \} $$
其中$S(i) = \sum\limits_{j =1}^i (C(j) + 1).$
然后把方程转化一下：$$f(i) = (S(i) - L - 1)^2 + \\ \min_{0 \leq j<i} \{-2(S(i)-L-1)S(j) + f(j) + S(j)^2 \}$$
就可以设$2(S(i)-L-1)$为斜率，$S(j)和 f(j) + S(j)^2$分别为横纵坐标建立凸包进行斜率优化，复杂度$O(NlogN)$.
最后可以发现每次对凸包进行二分查找时的斜率$2(S(i)-L-1)$是随i单调递增的……于是我们可以用单调队列优化到$O(n)$。
#include <cstdio>
template<typename T>inline ;
, c = getchar();
x = c - + c - }
typedef ;
, it2 = ;
LL S, X[maxn], Y[maxn], f[maxn];
(y<=Y[j])?:((k<)?:((x-X[j])*(Y[j]-Y[k]) >= (X[j]-X[k])*(y-Y[j])))
inline ){
X[it2] = x, Y[it2] = y;
++it2;
}
, it2-))--it2;
X[it2] = x, Y[it2] = y;
++it2;
}
inline LL k, t, b1, b2, y;
;i <= N;++i){
S += V[i];
t = S - L - , k = - t << ;
b2 = k * X[it1] + Y[it1];
){
f[i] = t * t + b2;
y = f[i] + S * S;
insert(S, y);
}
< it2){
b1 = b2, b2 = k * X[it1+] + Y[it1+];
}
f[i] = t * t + k * X[it1] + Y[it1];
y = f[i] + S * S;
insert(S, y);
}
printf( }
freopen( getd(N), getd(L);
;i <= N;++i)
getd(C), V[i] = C + ;
dp();
;
}
单调队列dp