DP中的优化

单调队列优化DP

划定区间取值问题
对于长度为l的区间，每s长度至少有一个数被取，使用动态规划
f(i)表示选第i个数的最小方案
集合划分：可以取i-s+1到i-1的各种方式
因此f[i]=w[i]+min(f[i-m+1],....,f[i-1])
对于后面这一段min(f[i-m+1~i-1])可以使用单调队列优化。

---

凸包优化DP（斜率优化）

$$由状态转移方程：f[i]=min\{ f[j]+T_{i}(C_i-C_j)+S(C_n-C_j) \}$$ $$其中j=0,1...i-1$$ $$我们可以将其整理为以C_j为自变量，f[j]为因变量的一次函数形式：$$ $$f(j)=(S+T_i)C_j+f(i)-T_iC_i-SC_n$$

因为要最小化f(i),对于本题来说，就是找截距最小值，在图中我们可以发现只需要维护图中的凸包的下边界：

$$凸包下边界的定义：任意两点连线，在连线上方的点都在凸包的下边界以上$$

但是只维护凸包的下边界最坏会出现O(n)的情况，因此仍然需要挖掘其他信息：

$$1.某点被取当为斜率大于k的第一个点的起点$$

总结：如何在维护凸包中找到截距最小的点：

相当于在于一个单调的队列中，找到第一个大于某一个数的点。因此普遍做法是采用二分法。

其他特殊性质：

1.斜率单调递增，新加的点的横坐标也单调递增(k1<k2<k3)

​ 在查询的时候可以将队头小于当前斜率的点全部删除(删除所有小于k的点)

​ 在插入的时候，把队尾所有不满足要求的点全部删除（即不在凸包上）

$$1. 若\ \ \ \frac{f_2-f_1}{C_2-C_1} \le sumT_i+S是则删除队头$$ $$2.若\ \ \frac{f_{tt}-f_{tt-1}}{C_{tt}-C_{tt-1}} \ge \frac{f_i-f_{tt}}{C_i-C_{tt}}则将队尾元素删去$$

例题：Acwing 301

更一般的情况，T<0时：

​ 此时k无法保证单调性，但新加的点横坐标一定单调递增。因此只能查询，不能删去斜率小于当前点的点。查询的时候只能二分；

​ 队尾仍然删除所有队尾不在凸包上的点

如果T>0,C<0 可以使用反函数，交换x,y

最一般的情况：

考虑C可能小于0且T也可能小于0

​ 队头处理还是二分。队尾的动态维护有序序列则需要平衡树来做了