DP优化
1.矩阵快速幂优化DP
当DP的转移可以用转移矩阵表示出来的时候，这个DP一般都是可以用矩阵快速幂来进行优化的
而且矩阵快速幂优化DP的特征非常的明显，一般是有一维状态数特别大，一维状态数特别小
然后建立转移矩阵的小技巧就是$trans_{i,j}$表示从状态i转移到状态j的贡献
然后矩阵快速幂还可以把乘法变成加法，加法变成取min/max，可以证明这样还是满足结合律的，实际的dp含义也不会被改变
是一种优化转移的很好的方式
当然，矩阵维护DP也可以扩展到动态DP，在这里跟题目无关就不讲了
2.数据结构优化DP
数据结构优化DP
一般都是直接在数据结构里面维护每个DP值（和那个位置上对应的贡献），这个时候需要把移动指针产生的贡献全部拆分开来，然后如果贡献的叠加范围是存在某个特殊的性质（比如区间，或者某个数的倍数）就可以选择相应的数据结构进行维护
数据结构的使用非常灵活，需要多加练习才可以熟练掌握
3.决策单调性优化
3.1 单调队列/单调栈优化
一种比较简单的实现形式，通常是有比较显然的决策单调性
通常有两种方式：
3.1.1 维护点值
数据结构中只需要存点，然后可以直接每次取维护的队首/栈顶来进行更新，维护简单
3.1.2 维护区间
我们发现每个决策点的最优贡献是一个区间
那么我们就维护一个很多个区间组成的队列
这个队列每次加入的时候就可以进行比较并维护
具体实现是这样的：
- 如果当前决策点在最后一个位置都不会比最后一个最优区间优秀，说明他没有贡献
- 如果比当前最后一个区间全部的位置都要更优就可以直接删除最后的区间
- 如果只比当前最后的区间的一部分更优就二分出当前结点比上一个节点优的最早的节点，并把从二分出的节点到末尾区间的最优贡献点变成当前结点
3.1.2的单调队列还可以用来维护四边形不等式优化的DP
3.2 斜率优化
斜率优化的一个典型形式就是$dp_{i}=dp_{j}+a_i*b_j+c_j$
这时候因为出现了$a_i*b_j$，所以如果可以优化一般都是斜率优化（大概是因为其他的优化方式都不涉及乘除）
然后就可以非常无脑的把这个式子用一次函数式表示出来
比如上面的这个式子经过移项变成$-a_i*b_j+dp_{i}=dp_j+c_j$
观察一下这个式子发现如果令
- $y = dp_j +c_j$
- $x=b_j$
- $k=-a_i$
- $b=dp_i$
那么原来的式子实际上就变成了$y=kx+b$
我们显然要求的就是截距b的某个极值
这样我们就可以把一个决策点j转化成二维平面上的一个点$(b_j,dp_j+c_j)$
我们每次要用斜率$-a_i$去截出一个最大的$dp_i$
很显然这个最优决策点一定存在于凸壳上面，所以直接用单调队列/单调栈维护出凸壳就可以了
然后根据题目看需不需要在凸壳上二分出最优的决策点就可以了
至于是上凸壳还是下凸壳，就可以根据k的单调性确定了
但是在x坐标$b_j$不单调的时候就只有使用3.2.2的方法了
3.3 分治优化
3.3.1 普通分治
有的时候我们不方便找到决策点但是可以知道，如果$i$的决策点是$p_i$，那么对于$j<i<k$有$p_j\le p_i\le p_k$
那我们直接对于mid包里找到$p_{min}$然后递归成区间求解就可以了
3.3.2 CDQ分治
这里对应斜率优化的时候$x$坐标不单调的情况
因为x不单调所以我们没有办法（其实也有办法）动态维护凸壳所以我们再用分治解决这个问题
首先选择一个mid，然后递归求解左边区间的问题，这个时候我们就已经知道了左边区间的所有的DP值
然后于是就可以把左边的所有点按照x归并排序之后建成凸壳并用右边的点进行询问，询问完了就可以继续递归右子区间进行解题了
分治复杂度是$nlogn$的
3.4 四边形不等式优化
看起来是最简单的结构，但是用到了最复杂的思想
一般是需要证明一个这样的式子：
$w_{i,j+1}+w_{i+1,j}\le w_{i, j}+ w_{i+1,j+1}$
所以就可以得到
$w_{i+1,j}-w_{i+1,j+1}\le w_{i,j}-w_{i,j+1}$
$w_{i,j+1}-w_{i+1,j+1}\le w_{i,j}-w_{i+1,j}$
推导出的通式就是：$对于i<i’\le j<j’,有w_{i,j}+w_{i’,j’}≤w_{i’,j}+w_{i,j’} $
然后对于一个常见的转移方程$dp_i=dp_j+w_{i,j}$
设i的决策点是$p_i$，那么i-1的决策点$p_{i-1}$一定满足：
任意的$k<p_{i-1}$
有$dp_{p_{i-1}}+w_{p_{i-1},i-1}\le dp_{k}+w_{k,i-1}$
即$w_{p_{i-1},i-1}-w_{k,i-1}\le dp_{k}-dp_{p_{i-1}}$
如果w满足平行四边形不等式，那么也一定有：
$w_{p_{i-1},i}-w_{k,i}\le dp_{k}-dp_{p_{i-1}}$
所以有$dp_{p_{i-1}}+w_{p_{i-1},i} \le dp_{k}+w_{k,i}$
就证明了单调性，因为这个东西也是区间覆盖
所以还是可以用单调队列进行维护的
完结撒花