【题目描述】
P教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。
他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。
P教授有编号为1...N的N件玩具，第i件玩具经过压缩后变成一维长度为$ C_i $.
为了方便整理，P教授要求在一个一维容器中的玩具编号是连续的。
同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物，形式地说如果将第$ i $件玩具到第$ j $个玩具放到一个容器中，那么容器的长度将为 $ x = j - i + \sum_{k = i}^j C_k $
制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为$ x $,其制作费用为$ (X - L)^2 $.其中$ L $是一个常量。
P教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过$ L $。但他希望费用最小.
【题目链接】
BZOJ 1010 玩具装箱Toy【HNOI 2008】
【普通DP】
斜率优化初探，我们首先来考虑一个普通DP。
设$f[i]$表示$[1, i]$的玩具装箱的最小代价，考虑将哪些玩具和$ i $放一起，设是将$ [j, i] $放在统一容器中，易得转移：
$$ f[i] = min\{ \ f[j - 1] + (i - j + s_i - s_{j - 1} - L)^2 \ \} \ j \in [1, i]$$
直接枚举$ j $转移，总复杂度是$O(n^2)$的。
那么新技能来啦，斜率优化！
【斜率？】
我们要分析决策之间的关系。
先来推一波式子，
记决策 $ j $的决策费用为$ F(j) $，即， $$ F(j) = f[j - 1] + (i - j + s_i - s_{j - 1} - L)^2 $$
我们将平方项展开，然后使$ i $和$ j $尽量分离——然而并不要展开后再分离，五项的完全平方一点都不好玩，所以可以先分离后展开，
记， $$ h(i) = i + s_i - L$$ $$ x(j) = s_{j - 1} + j$$ 则有， $$ F(j) = f[j - 1] + (h(i) - x(j))^2 $$ 展开得， $$ F(j) = f[j - 1] + x(j) ^ 2 + h(i) ^ 2 - 2h(i)x(j) $$ 大概就只能分离成这样子了， $ -2h(i)x(j) $一项无法分离。
那么考虑两个可行决策$ j_1, j_2 $孰优孰劣，不妨设$ j_1 < j_2 $，然后研究$j_2$优于$j_1$，即$ F(j_2) < F(j_1) $的充要条件。
那么我们有：
$$ f[j_2 - 1] + x(j_2) ^ 2 + h(i) ^ 2 - 2h(i)x(j_2) < f[j_1 - 1] + x(j_1) ^ 2 + h(i) ^ 2 - 2h(i)x(j_1) $$
整理，得，
$$ ( f[j_2 - 1] + x(j_2)^2 ) - ( f[j_1 - 1] + x(j_1)^2 ) < 2h(i)(x(j_2) - x(j_1)) $$
为简洁，设$y(i) = f[i - 1] + x(i)^2 $，则有，
$$ y(j_2) - y(j_1) < 2h(i)(x(j_2) - x(j_1))$$
我们知道，$x(j)$是单调增的，所以除过来，就有，
$$ \frac { y(j_2) - y(j_1) } {x(j_2) - x(j_1)} < 2h(i) $$
嗯，终于见到斜率了，斜率优化这个名字没骗人。
记斜率， $$ Slope(j_1, j_2) = \frac { y(j_2) - y(j_1) } {x(j_2) - x(j_1)} $$
就这样，我们得到了当$ j_1 < j_2 $时，$ j_2 $比$ j_1 $优的充要条件，也就是说：
$$ Slope(j_1, j_2) < 2h(i) \Leftrightarrow F(j_2) < F(j_1) $$
【优化？】
所以得到了斜率，可怎么来优化呢？
第一，以一个队列来维护可选决策，删除冗余决策，只储存有价值的决策，使得任意$j_k, j_{k + 1}$总有$ Slope(j_k, j_{k + 1}) > 2h(i) $，这样，最优决策总是在队首。
为什么不满足该条件的决策是冗余的呢？
简要证明，如果在计算过程中出现了决策$a, b$，使得$ Slope(a, b) < 2h(i) $，能说明些什么呢？
说明$ b $比$ a $更优，而且，由于$ 2h(i) $是单调增的，所以对于$ \forall i' > i $，总有$ Slope(a, b) < 2h(i) < 2h(i') $，也就是说，$ b $永远比$ a $优！故$ a $是冗余决策，可以删除。
证毕。
第二，可以维护相邻决策之间的斜率单调增。
简要证明，设依次有三个相邻决策$j_1, j_2, j_3$，如果$j_2$想要成为最优决策，那么必然要满足： $$ Slope(j_1, j_2) < 2h(i) \\ Slope(j_2, j_3) > 2h(i) $$ 那么有， $$ Slope(j_1, j_2) < Slope(j_2, j_3) $$ 也就是说$ j_2 $使得斜率单调增，这样的决策才有价值保留，若$j_2$使得决策单调减，则其必不可能成为最优决策，可以删除。
证毕。
说了这么长，其实核心代码很简单：
static int Q[MAXN];
int l = 0, r = -1;
for(int i = 1; i <= n; i++){
while(l < r && slope(Q[r - 1], Q[r]) > slope(Q[r], i)) r--;
Q[++r] = i;
while(l < r && slope(Q[l], Q[l + 1]) < 2 * h(i)) l++;
int j = Q[l];
f[i] = f[j - 1] + sqr(j - i + c[i] - c[j - 1] - L);
}
(代码高亮莫名炸了不知所措QwQ,正在检查...)
时间复杂度$O(n)$，因为每个决策最多被删除一次。
【AC代码】
#include <cstdio>
#include <climits>
#include <algorithm>
const int MAXN = 50061;
typedef long long int64;
int n, L;
int64 c[MAXN];
inline int64 sqr(int64 x){
return x * x;
}
int64 f[MAXN];
inline int64 x(int64 i){
return i + c[i - 1];
}
inline int64 y(int64 i){
return f[i - 1] + sqr(x(i));
}
inline double slope(int i, int j){
return (double)(y(j) - y(i)) / (x(j) - x(i));
}
inline int64 h(int i){
return i + c[i] - L;
}
inline void dp(){
static int Q[MAXN];
int l = 0, r = -1;
for(int i = 1; i <= n; i++){
while(l < r && slope(Q[r - 1], Q[r]) > slope(Q[r], i)) r--;
Q[++r] = i;
while(l < r && slope(Q[l], Q[l + 1]) < 2 * h(i)) l++;
int j = Q[l];
f[i] = f[j - 1] + sqr(j - i + c[i] - c[j - 1] - L);
}
}
int main(){
scanf("%d%d", &n, &L);
c[0] = 0;
for(int i = 1; i <= n; i++) scanf("%lld", c + i), c[i] += c[i - 1];
dp();
printf("%lld\n", f[n]);
return 0;
}
就是这样啦。