单调队列

本来对于动态规划我是弃疗的。不过发现单调队列没那么吓人,其实就是个滑动窗口最值问题。
还有就是chenyao的ppt写错了……坑
贴的这个没错

通常做dp的时候f[i]的值依赖从前面K个状态转移过来
由于K的限制,所以并不能全部点均从一个点转移过来
需要维护最优点,次优点,….
同时如果对于f[i] 和 f[j],i < j 且从f[j]转移更优,此时f[i]一定没有用
所以我们维护的点中,位置必须为单调增,贡献的值为单调减
by chenyao

anyway,单调队列能优化的方程一般都长这样:
$$f[i] = \max{f[j] + c[j]}, i - a \le j \le i - b$$
$f$ 是状态,$c$ 是一个常数数组。
如果你会滑动窗口肯定懂 $b=1$ 时怎么做,然后发现 $b \ne 1$ 时只需在每次循环开始时尝试入队往前数的第 b 个状态即可。
不懂滑动窗口就先去学那个。lrj 的书上不知道哪有来着。
然后需要说明的是题目的方程一般都不会长这么简洁,所以你一般需要把 $j$ 相关的量放到一起,再把 $i$ 相关的量放到一起。每次转移时仅与 $i$ 有关的量可以拿到 $\max$ 外面,于是就可以得到上面这种形式。

实例!

解决

还是举个例子更好。
为了抵制bzoj进行垄断,我选择链接cogs上相同的题!
USACO Open11 修剪草坪 from COGS

简要题意:n 个数中选一些数,并且不能选连续的 k 个数,要求选的数和最大。n,k <= 1e5, 数在 long long

设 $f[i]$ 是前 i 个数的答案,那么可以从 $f[j]$ 转移过来,决策是选择 $[j + 2, i]$ 这些数。
方程:
$$f[i] = \max{f[j] + sum[i] - sum[j + 1]}, i -(j + 2) + 1\le k\Rightarrow i - j - 1 \le k$$
注意这个方程考虑了不选 $i$ 的情况,此时 $j - 1$。
一看见这种东西都是顺手前缀和的……
暴力转移 $O(nk)$,接下来我们把它优化到$O(n)$
我们使用高级数学方法——小学的加法交换律和加法结合律!
$$f[i] = \max{f[j] - sum[j + 1]} + sum[i]$$
看!是不是和最开始的方程形式一样了!
如果说和最原始的滑动窗口哪里不一样的话,就是滑动窗口在一个数组上滑,也在这个数组上赋值。而单调队列优化dp在 $f$ 上赋值,然后把 $f + c$ 放到被滑的那个数组里。

代码

//修剪草坪
#include <cstdio>
#include <algorithm>
#define file(x) "mowlawn." #x
typedef long long ll;
using std::max;
const int N = 1e5 + 10;
int n, k, head, tail;
ll f[N], a[N], ans;
struct D{int i;ll v;}q[N];
int main() {
    freopen(file(in), "r", stdin);
    freopen(file(out), "w", stdout);
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%lld", a + i), a[i] += a[i - 1];
    q[tail++] = (D){-1, 0};//考虑清楚怎么样才不会漏决策!这个决策代表选一个前缀
    for (int i = 1; i <= n; i++) {
        while (head != tail && i - q[head].i - 1 > k) head++;
        while (head != tail && q[tail - 1].v < f[i - 1] - a[i]) tail--;
        q[tail++] = (D){i - 1, f[i - 1] - a[i]};
        f[i] = q[head].v + a[i];
        ans = max(ans, f[i]);
    }
    printf("%lld", ans);
}

实例!!

SCOI2010 股票交易 from 洛谷
这些题bzoj都有,貌似都是权限

解决

题意自己看吧。
然后方程我懒得写了,又不难。
注意到这次变成二维了。股票交易
对于每一天都可以做两(买卖)次单调队列,第 i 天的窗口在 i - w - 1天上。

代码

//SCOI2010 股票交易
#include <cstdio>
#include <algorithm>
#include <cstring>
using std::max;
const int N = 2010;
int n, w, p, as[N], bs[N], ap[N], bp[N], f[N][N], head, tail, q[N];
//yesterday(反正是以前), have, today, now have
inline int buy(int yes, int hv, int tod, int now) {
    return f[yes][hv] - (now - hv)*ap[tod];
}
inline int sell(int yes, int hv, int tod, int now) {
    return f[yes][hv] + (hv - now)*bp[tod];
}
int main() {
//    freopen("input", "r", stdin);
    scanf("%d%d%d", &n, &p, &w);
    for (int i = 1; i <= n; i++) scanf("%d%d%d%d", ap + i, bp + i, as + i, bs + i);
    memset(f, 0xc0, sizeof(f));//不能达到的状态收益负无穷
    f[0][0] = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= p; j++) f[i][j] = f[i - 1][j];//不买不卖
        head = tail = 0;
        for (int j = 1; j <= p; j++) {
            while (head != tail && q[head] < j - as[i]) head++;
            while (head != tail && buy(max(i - w - 1, 0), q[tail - 1], i, j) < buy(max(i - w - 1, 0), j - 1, i, j)) tail--;
            q[tail++] = j - 1;
            f[i][j] = max(f[i][j], buy(max(i - w - 1, 0), q[head], i, j));
        }
        head = tail = 0;
        for (int j = p - 1; j >= 0; j--) {
            while (head != tail && q[head] > j + bs[i]) head++;
            while (head != tail && sell(max(i - w - 1, 0), q[tail - 1], i, j) < sell(max(i - w - 1, 0), j + 1, i, j)) tail--;
            q[tail++] = j + 1;
            f[i][j] = max(f[i][j], sell(max(i - w - 1, 0), q[head], i, j));
        }
    }
    printf("%d\n", f[n][0]);
}

斜率优化

学斜率优化……主要是你需要克服公式恐惧症

初级

这方面的变形比较多,如果我写错了,或者你觉得哪里不太清楚,欢迎评论
来几个水题爽爽。


HNOI2008 玩具装箱
dp方程真的好写。
$$f[i] = \max_{j < i}{f[j] + (i - j - 1 + s[i] - s[j] - l)^2}$$
$f$是答案,$s$为前缀和。
然后找到 $i$ 点的两个决策 $j,k$ 使得 $j < k$ 并且 $k$ 优于 $j$。
于是带入转移方程即得
$$f[j] + (i - j - 1 + s[i] - s[j] - l)^2 < f[k] + (i - k - 1 + s[i] - s[k] - l)^2$$
然后我们的工作就是要把它左边化成形如$\frac{y_j - y_k}{x_j - x_k}$的式子。
于是得到:
$$\frac{f[j] + (j + s[i])^2 - f[k] - (k + s[i])^2}{(j + s[j] - k - s[k])} < 2(i + s[i] - l)$$
注意中间由于除数为负变了一次不等式方向
所以左边成为形如$(x + s[x], f[x] + (x + s[x])^2)$这样的两个点的斜率。
注意我们一直进行恒等变形。
也就是说,对于 $k$ 优于 $j$ 且 $j < k$ 的的决策都满足上式。
下证有效决策集在一个下凸包上。

此时考虑上凸的三个点j1, j2, j3,即slope(j1, j2) > slope(j2, j3)
此时若slope(j1, j2) < 2g[i],那么j2比j1优,但此时j3一定比j2优
若slope(j1, j2) >= 2
g[i],则j1比j2优
所以前面的点如过画在平面二位直角坐标系上,一定只有下凸包上的点有意义
by chenyao

然后我们需要在dp时维护这样一个凸包。这道题中插入的点的$x$坐标是单调递增的。所以我们可以用单调队列维护凸包。
每次计算队首两个点的斜率,若满足上式则弹出队首。否则队首即为最优决策。
我们来证明一下队首即为最优决策的正确性:
首先经过一些弹出,队首两个点一定不满足上式了。所以有$slope(q[head], q[head + 1)] >= \dots$,然后我们通过上凸包的图像发现,一个点到它右边若干点的斜率是单减的,所以队首点对队中所有点都不满足上式,于是队首即为最优决策。

//玩具装箱
#include <cstdio>
typedef long long ll;
const int N = 5e4 + 10;
int n, q[N], sz, head, tail;
ll f[N], c[N], l;
inline double y(ll i) {return f[i] + (i + c[i])*1.0*(i + c[i]);}
inline double x(ll i) {return i + c[i];}
inline double slope(int j, int k) {//j < k
    return (y(j) - y(k))/(x(j) - x(k));
}
inline ll sq(ll x) {return x*x;}
int main() {
    freopen("bzoj_1010.in", "r", stdin);
    freopen("bzoj_1010.out", "w", stdout);
    scanf("%d%lld", &n, &l);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", c + i), c[i] += c[i - 1];
        while (head + 1 != tail && slope(q[tail - 2], q[tail - 1]) > slope(q[tail - 1], i - 1)) tail--;
        q[tail++] = i - 1;
        while (head + 1 != tail && slope(q[head], q[head + 1]) < 2*(i + c[i] - l)) head++;
        int j = q[head];
        f[i] = f[j] + sq(i - j - 1 + c[i] - c[j] - l);
    }
    printf("%lld", f[n]);
}
Prob Hint
1010 HNOI2008 玩具装箱toy
4518 SDOI2016 征途 最简单的
1911 Apio2010 特别行动队 可见对二次函数型的代价都适用
1096 ZJOI2007 仓库建设 中等
1597 Usaco2008Mar 土地购买 不会的话就查题解吧……难点不在斜率优化的变形上
3156 防御准备 随便写写

中等

NOI2007 货币兑换cash
首先你要会cdq分治。
然后明白cdq分治本质是计算左半部分对右半部分的影响。

如果你对cdq分治处理dp不太理解可以先做hackrank的一道题,101hack这个比赛的Maximizing Mission Points。
这个网站上有这个题的题解。

然后你可以看cdq的那篇论文。

然后你可以看看hzwer的代码。他的带注释。他的空间还比论文优一个log。
可惜他的状态定义不太优美,是a货币的数目。并且代码有些细节是错的。

所以我贴下我的代码。
我的状态定义就是最大收益。

//货币兑换
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using std::max;
const int N = 1e6 + 10;
const double EPS = 1e-7;
int n, sk[N];
double f[N], s, a[N], b[N], rate[N];
struct P{int i;double x, y, d;
    bool operator<(const P& b)const {return d > b.d;}
    inline void init() {
        x = f[i]/(b[i] + rate[i]*a[i]);
        y = f[i]*rate[i]/(b[i] + rate[i]*a[i]);
    }
}p[N], q[N];
double slope(int i, int j) {
    if (fabs(p[i].x - p[j].x) < EPS) return 1e20;
    return (p[i].y - p[j].y)/(p[i].x - p[j].x);
}
void solve(int l, int r) {
    if (l == r) {
        f[l] = max(f[l], f[l - 1]);
        p[l].init();
        return;
    }
    int mid = (l + r) >> 1;
    for (int k = l, i = 0, j = mid - l + 1; k <= r; k++) q[(p[k].i <= mid ? i : j)++] = p[k];
    memcpy(p + l, q, (r - l + 1)*sizeof(P));
    solve(l, mid);
    int top = 0;
    for (int i = l; i <= mid; i++) {
        while (top > 1 && slope(sk[top], sk[top - 1]) < slope(sk[top], i)) top--;
        sk[++top] = i;
    }
    for (int x = 1, y = mid + 1; y <= r; y++) {
        while (x < top && slope(sk[x], sk[x + 1]) + EPS > p[y].d) x++;
        int i = p[y].i, j = sk[x];
        f[i] = max(f[i], p[j].x*b[i] + p[j].y*a[i]);
    }
    solve(mid + 1, r);
    int tot = 0;
    for (int i = l, j = mid + 1; i <= mid || j <= r; tot++) {
        if (i > mid || (j <= r && p[j].x < p[i].x)) q[tot] = p[j++];
        else q[tot] = p[i++];
    }
    memcpy(p + l, q, tot*sizeof(P));
}
int main() {
    freopen("cash.in", "r", stdin);
    freopen("cash.out", "w", stdout);
    scanf("%d%lf", &n, f);
    for (int i = 1; i <= n; i++) scanf("%lf%lf%lf", a + i, b + i, rate + i), p[i].d = -b[i]/a[i], p[i].i = i;
    std::sort(p + 1, p + 1 + n);
    solve(1, n);
    printf("%.3lf\n", f[n]);
}