决策单调性优化dp
很早之前看李煜东蓝书的时候被吓到了，现在来补一下。
- 前置芝士
决策单调性前提：最优化dp。通俗地讲就是每个状态只能由一个最优地状态转移而来。
决策单调性：状态的最优转移点单调，形式化地说就是。
四边形不等式：有函数 $w(x,y)$，令 $a\le b \le c \le d$，若其满足 $w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ 则称函数 $w(x,y)$ 满足四边形不等式。
决策单调性与四边形不等式的关系：考虑形如 $dp(i)=\min\left\{dp(j)+w(j,i)\right\}$ 的dp，若 $w(j,i)$ 满足四边形不等式，则此dp满足决策单调性。
那么我们怎么通过决策单调性优化dp呢，这有很多种方式。
- 分治优化决策单调性dp
前提1：二维dp，且只有前一层向后一层转换，同一层之间不会转换，一般也可以使用线段树等数据结构优化。
前提2：同一层内满足决策单调性。
满足这两个条件之后就可以进行分治了。
令 $l,r$ 为分治的边界，$mid$ 为 $l,r$ 中点，则我们可以先转移 $mid$ 。
令 $L,R$ 为决策候选区间的边界，我们在转移 $mid$ 之后可以得到一个最优转移点 $p$。
那么不难证明 $[l,mid-1]$ 的最优决策点在 $[L,p]$ 之间，$[mid+1,r]$ 的最优决策点在 $[p,R]$ 之间。
就可以分治了，总决策区间长度为 $O(n\log n)$ ，总候选区间长度为 $O(n\log n)$ ，总时间复杂度为 $O(n\log n)$。
例题：
这道题中还使用了一个小技巧，在计算 $w(i,j)$ 函数的时候，使用类似于莫队的双指针维护，观察所覆盖的区间范围，不难发现移动次数为 $O(候选区间长度)$ ，因而时间复杂度为 $O(n\log n)$ 。
比较板，但似乎有线性做法？
- 二分队列优化决策单调性dp
优化形如 $f_i=\min\limits^{i-1}_{j=0/1} \left\{f_j +w(i,j)\right\}$ 的dp方程。
根据决策单调性的定义，一个点的最优决策区间是不断右移的，只会被后面的区间反超。
那么为我们维护一个单调队列，队列中的点大小关系递减，所包含区间递增，我们更新时取队头即可。
那么如何维护这个单调队列呢，想象我们到了位置 $i$ ，那么从队尾开始，如果有一个点决策区间的左边界不如用 $i$ 更优，那么根据定义，这个点绝不可能比 $i$ 更优，因此弹出。
如果有点的决策区间一部分比 $i$ 优，一部分不比 $i$ 优，那么简单，把比 $i$ 优的区间设为新区间即可。
例题：
[NOI2009] 诗人小G 十分甚至九分地板。
- 二分栈优化决策单调性(?)dp
与上文的二分队列优化相反，每一种决策只会被更前面的决策所反超，因此不是传统意义上的决策单调性。
咕咕咕/
- 包含单调优化区间dp
部分内容摘自 OI Wiki。
一般情况下区间dp形如 $f_{l,r}=\min\limits^{r-1}_{k=l}\left\{f_{l,k}+f_{k+1,r} \right\}+w(l,r)$
前提1：$w(l,r)$ 满足区间包含单调性，即对于任意 $l\le l^{'}\le r^{'} \le r$，满足 $w(l^{'},r^{'})\le w(l,r)$。
前提2：$w(l,r)$ 满足四边形不等式。
若满足两个前提，则 $f_{l,r}$ 满足四边形不等式。
性质：若 $f_{l,r}$ 满足四边形不等式，令 $g_{l,r}$ 为 $f_{l,r}$ 的最优转移点，则 $g_{l,r-1}\le g_{l,r}\le g_{l+1,r}$。
在区间dp的同时记录最优转移点，则对于每一长度的转移点枚举时间复杂度为 $O(n)$ ，总时间负杂度为 $O(n^2)$ 。
例题：
比较特殊，只需要计算 $[1,i]$ 区间的dp值即可，但依旧可以套用上述结论，不同的是后半部分不能使用了，但这个整体又满足普通的决策单调性，另一半取 $\le g_{i+1,j}$ 即可。
斜率优化dp
斜率优化有很多理解方法，这里所记述的是其中一种普遍使用的。
斜率优化一般又来优化形如 $dp_i=\max\left\{ dp_j +(a_i-b_j)^2\right\}$ 的 dp 式子。
我们令：
拆开得到：
在 $i$ 固定时，若 $j,k$ 满足这个条件，则 $j$ 一定比 $k$ 更优。
将其投射到二维平面上，将其抽象为两个点，那么当 $j,k$ 间斜率大于 $2a_i$ 时，就说明 $j$ 更优。
在大多数题目中，给出的斜率都是单调的，我们可以用单调队列维护斜率，就相当于维护一个凸包。
对队首的限制就是上式，队尾的限制就是斜率递增，每次弹出队首即可。
例题：[CEOI2004] 锯木厂选址，[ZJOI2007] 仓库建设，[HNOI2008]玩具装箱。
进阶：当给出的斜率不递增时，应该怎么办？
实际上，我们依旧可以维护一个凸包，不过不同于单调队列，维护一整个凸包。
这个可以通过平衡树/李超树/cdq分治实现，但是对于NOIP用处不大，不多赘述。
WQS 二分
通过二分斜率来优化 dp 过程的一种方法，又称 dp 凸优化。
**使用WQS二分的前提：**dp 图像斜率递增，即是一个凸包。
具体的说，我们把 $(i,dp_i)$ 的图像绘制出来，如果形如一个凸包，则成立。
一般的，直接求解这种 $dp$ 的复杂度是很高的，无法接受，例如我们要求出 $dp_k$ ，而每个一个 $dp$ 数组所需的时间为 $O(n)$，则总时间复杂度为 $O(nk)$。
考虑利用凸包的性质进行优化，即我们二分一个斜率，求出这根直线与凸包的切点的坐标(同时包括横纵坐标)，不难发现这对 $k$ 是单调的。
这样当我们切到横坐标为 $k$ 的点时，得到的即为答案。
由于每一次所需的时间仍未 $O(n)$，因此总的时间复杂度为 $O(n\log k)$。
一般当我们求解的问题，斜率都可以抽象为个数等具体的数值，为整数，不需要考虑精度，考虑精度的话要注意上下界和题目要求吻合。
WQS 二分的经典应用：求解恰好选择 $k$ 个的问题，一般有这种要么是反演要么是WQS二分。
**注意点：**在绝大多数的情况下，WQS 二分的辅助 DP 过程中，必须要求出选几个时最优，才能调整二分上下界。
特殊情况：三点共线
有一些特定情况下，斜率不严格单调递增，因此我们有一定概率得不到自己想要的答案，这个时候很简单，只需要根据题目要求(最大/最小)，选择左右端点即可。
例题：
很有意思的题目，是和树形dp结合，我们考虑最朴素的dp方程，然后感性证明关于 k 是一个凸包，套用wqs二分即可，从这道题上也可以看出，WQS二分的应用是极为广泛和灵活的。
P5308 [COCI2018-2019#4] Akvizna
考虑朴素dp，不论是正着来还是倒着来都是可以的，不难发现可以斜率优化，可以做到 $O(n k)$。
然后经典的恰好 $k$ 个，上 WQS 二分，时间复杂度 $O(n\log k)$，注意卡一下精度。