决策单调性优化
目前只知道应用于形如 \(f_i=min{g_j+w(j,i)}\) 的式子。
四边形不等式
对于函数 \(f(x,y)\)，若其对于任意 \(l_1\le l_2\le r_2\le r_1\) 有 \(f(l_1,r_2)+f(l_2,r_1)\le f(l_1,r_1)+f(l_2,r_2)\)，我们称其满足四边形不等式。简记为交叉不大于包含。
斜率优化
目前只知道应用于对前面的一些 dp 值取 max/min 转移时使用。
一种比较通用的是如果 \(i\) 从 \(j\) 转移来的转移式能够化为与 \(i\) 相关的某项和与 \(j\) 相关的某项的乘积加上与 \(j\) 相关的某项再加上与 \(j\) 无关的项，会发现前面三个组成一个形如 \(kx+b\) 的一次函数形式，将与 \(j\) 有关的项当做 \(k,b\)，查询 \(x=\) 与 \(i\) 有关的项时的最值。然后套上李超树进行转移。
感觉适用范围很广，在做过的为数不多的斜率题里面都是可以用李超树优化的。而且板子会背也不难写。
标签：le,某项,笔记,优化,转移,dp,李超树 From： https://www.cnblogs.com/Zsq20100122/p/18555412