对于一维 dp 中例如
这样的转移方程，显然对于一个 \(dp_i\)，就像求 LIS 的线段树优化 dp 那样，它是由某一个 \(dp_j\) 转移而来。令 \(p_i\) 为使得这个式子取得最小值的 \(j\) 的值，那么这个 \(p_i\) 便是 \(dp_i\) 的最优决策。类似于斜率优化，我们要做的是维护这个最优决策集合。
并不是所有的方程都可以这样去做。在这种形式的方程中，只有满足决策单调性的才可以去使用这种方法。决策单调性是指 \(p_i\) 单调不减，通俗的讲，就是随着时间的推移（\(i\) 的增大），当前的最优决策点（即 \(p_i\)）只会增大。
先不考虑如何去证明决策单调性。朴素做上式的复杂度是 \(\mathcal{O}(n^2)\)，如果能够利用决策单调性，对 \(p\) 进行维护，在求解时可以调用当前的最优决策计算出 \(dp\)，复杂度将会大大降低。不难想到可以用 \(dp\) 来更新 \(p\)，通俗的讲就是：每求出一个 \(dp\) 值，计算当前点可以成为哪些点的最优决策，然后把这些点的最优决策改为当前点。由于决策单调性，一个点所更新的，可以是 \(p\) 的一段后缀。
假设当前点为 \(k\)，如果存在两个点 \(i<j\) 且 \(p_i=k\) 而 \(p_j\) 没有被更新，由于决策单调性，在最终的 \(p\) 中 \(k\leq p_i \leq p_j\)。
- 若 \(k\) 优于（或等于）当前的 \(p_j\)，它就会被更新。
- 若 \(k\) 劣于当前的 \(p_j\)，在最终结果中，它不管有没有被覆盖，都一定会被更新掉。
由于 \(p\) 具有单调性，很容易想到二分。若当前点为 \(dp_i\)，在更新的时候二分出最小的“\(i\) 优于 \(p_j\)”的位置 \(j\)，然后将 \([j , n]\) 全部覆盖为 \(i\)。
用这样的方法，上述一维 dp 的式子可以在 \(\mathcal{O}(n \log n)\) 内求出。
原文：https://www.cnblogs.com/xiong-6/p/14271749.html