在一维线性动态规划里，我们经常见到形如 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 了……
递推是按照一定的规律来计算序列中的每个项，通常是通过计算前面的一些项来得出序列中的指定项的值。其思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法利用了计算机速度快和不知疲倦的机器特点。
最近准备刷刷BZOJ上的水题……
物流公司要把一批货物从码头A运到码头B。由于货物量比较大，需要n天才能运完。货物运输过程中一般要转停好几个码头。物流公司通常会设计一条固定的运输路线，以便对整个运输过程实施严格的管理和跟踪。由于各种因素的存在，有的时候某个码头会无法装卸货物。这时候就必须修改运输路线，让货物能够按时到达目的地。但是修改路线是一件十分麻烦的事情，会带来额外的成本。因此物流公司希望能够订一个n天的运输计划，使得总成本尽可能地小。
又是超级水的一题，一道线性DP。
这几道DP很简单，分成很多篇文章发可以假装自己的博客写了很多文章～