在一维线性动态规划里，我们经常见到形如 $f(i)=min/max(f(j)+c_i)$（其实可以看成 $f(i)=min/max(a_i+b_j)$ ）这样形式的转移方程。朴素做法是 $\Theta (N^2)$。显然这样的形式可以用单调队列维护，优化到 $\Theta (N)$。但是如果遇到 $f(i)=min/max(a_i\ast b_j+c_i+d_j)$ 这样的，似乎用单调队列就难以维护了……因为 $a_i\ast b_j$ 既与 $i$ 有关，又与 $j$ 有关。这时候就要用到另一种优化方式：斜率优化。
斜率优化小结
递推专项训练五题题解
今天的 XY 题居然是递推专题，五道题目全都是递推，30+个人 AK 了……
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
BZOJ1003 物流运输 题解
最近准备刷刷BZOJ上的水题……
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。