探秘——如何优化

1. 优化状态总数：改变状态表示方式、选择适当的枚举顺序

2. 优化每个状态的转移时间：四边形不等式和决策的单调性、减少决策量、减少决策时间、减少计算贡献的时间

对于这一类的题目，仔细辨别出条件或决策下的隐藏信息是很重要的。

很多分享都只是在技术上介绍了这一些方法却没有给出实际场景的演示或者是这些算法背后的关联。本文将尽力避免这一类情况。

具体解释——何为单调，何为单调算法的关联？

常见的单调主要包括区间单调递增或递减但实际上很多问题都不会满足这一点，这个时候需要找到题目隐藏的单调性，比如: 单调队列优化DP 就是根据决策点单调的性质，$O(n)$次出队入队来优化，此外，还有像单调栈可以求解出每一个元素接下来的最大值和最小值，如果有DP以这个为阶段就可以进行优化了。

丹钓战

使用单调栈算法可以算出一个数被弹出的时候。

然后询问需要判断到底到那个数时所有都会被弹出去。

因为是所有都被弹出去，等价于第一个数什么时候被弹出去。

单调栈+倍增解决即可。

进阶——决策单调性的扩展延申

以上算法是对决策点的单调性的注意，如何维护合法决策点是DP优化的核心内容。作为解释：常见的斜率优化和四边形不等式会提供一种思路。

请注意的是斜率优化和四边形不等式是不重合的，最好的区分方式是区分它们优化的DP方程类型，下面我列出了不同方程类型对应的优化方法。

示范

你可以发现四边形不等式是对区间w(i,j)贡献的单调性的计算。

而斜率优化是在观察到单调性之后进行的优化。