次次学次次忘，这次必须记录一下。
斜率优化dp
概念：
对于形如:
\[dp_i=\min/\max (dp_j+a_i\times b_j+c_i+d_j) \]的dp式子，将复杂度从 \(O(n^2)\) 优化到接近 \(O(n)\) 的优化方式。
注：\(a_i\) 和 \(c_i\) 就是和 \(i\) 有关的变量，\(b_j\) 和 \(d_j\) 就是和 \(j\) 有关的变量。
方法：
斜率优化dp有两种理解和实现的方法，但是殊途同归，最终都是一样的，将式子转化成形如 \(y=kx+b\) 的二元一次方程的形式，之后再利用凸包来优化。
接下来我就用最简单的一个式子作为示例来讲解。
dp示例：
\[dp_i=\min _{j=1}^{i-1}(dp_j - i\times j + i + j) \]理解方法1：
假设 \(i\) 最优秀的转移方式就是从 \(j\) 转移过来，则：
\[dp_i=dp_j - i\times j + i + j \]式子可以转化成：
\[( dp_j + j ) = i\times j + ( dp_i - i ) \]（秘诀就是将只和 \(j\) 有关的量放在一起，只和 \(i\) 相关的变量放在一起）
这就很像一个二元一次方程，我们可以设 \(( dp_j + j )\) 为 \(y\)，\(j\) 就是 \(x\)，而 \(i\) 就是斜率 \(k\)，而剩下的 \((dp_i - i)\) 就是 \(b\)——截距。
那么，我们目标就是得到最小的 \(dp_i\) ，即 \((dp_i - i)\) 最小，即为求一个满足条件的 \(j\)，使得最后求出来的方程的截距最小。
那么，我们就可以把问题看成：
在一个平面直接坐标系中每一个dp值都对应着一个点，坐标为 \((\ j , dp_j + j\ )\)，对于每一次转移，都是有一个斜率为 \(i\) 的直线，只要有某个点在这条直线上，这次转移就是有效的，我们想要截距最小。
（放个图方便理解）
所以我们考虑，怎么样才能快速的找到最优的那个转移点。
可以发现，我们首先想让截距最小，所以这条直线肯定是越往下越好，其次还发现这条线的斜率是固定的（只与 \(i\) 相关）。
那么形象一点考虑就是一条线从下往上去截，直到截到了某个点，那这个点就是答案。
（还是图片更一目了然）
这时候可以发现，只有最下面的一圈点会有可能产生贡献，即一定是相邻两点斜率单调且尽可能小。
如图，2号点就肯定不会是最优的用来转移的点，因为 \(k_1>k_2\)。
然后，有可能用于转移的点就是 \(4，1，3\)。
这其实就是个下凸包，直接用电调队列维护一个斜率单调的凸包，每次转移直接从凸包上查找，并且一定是从斜率大于 \(k\) 和小于 \(k\) 的线之间的交界的点转移。
注：\(k\) 就是当前转移直线的斜率。
（看图）
注：红色的点就是所维护的凸包，蓝色的点就是其它的一定不会产生贡献的点，与红色的点所切的点就是用于转移的点。
标签：截距,斜率,就是,优化,转移,dp From： https://www.cnblogs.com/Jack-YT/p/18352209