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

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

anyway，单调队列能优化的方程一般都长这样：

$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]$ 这些数。
方程：

注意这个方程考虑了不选 $i$ 的情况，此时 $j - 1$。
一看见这种东西都是顺手前缀和的……
暴力转移 $O(nk)$，接下来我们把它优化到$O(n)$
我们使用高级数学方法——小学的加法交换律和加法结合律！

看！是不是和最开始的方程形式一样了！
如果说和最原始的滑动窗口哪里不一样的话，就是滑动窗口在一个数组上滑，也在这个数组上赋值。而单调队列优化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$是答案，$s$为前缀和。
然后找到 $i$ 点的两个决策 $j,k$ 使得 $j < k$ 并且 $k$ 优于 $j$。
于是带入转移方程即得

然后我们的工作就是要把它左边化成形如$\frac{y_j - y_k}{x_j - x_k}$的式子。
于是得到：

注意中间由于除数为负变了一次不等式方向
所以左边成为形如$(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) >= 2g[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]);
}