前言
本文将介绍决策单调性优化 DP 的相关内容。持续更新修正,如有差错请指出。
1.四边形不等式优化
1.1 四边形不等式与决策单调性
- 四边形不等式:如果对于任意的 \(a \le b \le c \le d\) 均成立
则称代价函数 \(w\) 满足四边形不等式。观察上述形式,即包含劣于相交,注意这是当我们要求代价函数 \(w\) 最小时四边形不等式的符号,如果我们要求 \(w\) 最大,相当于对其取相反数,那么相应的,此时的四边形不等式需要变号。
四边形不等式优化利用的是状态转移方程中的决策单调性,通常用于解决一系列的最优化问题。
在解决动态规划相关问题的时候,通常会遇到以下这种形式
其中 \(\min\) 也可能是 \(\max\)。一般情形下,这类问题解决的时间复杂度为 \(\mathcal{O(n^2)}\),如果 \(f\) 具有决策单调性,那么就可以将时间复杂度优化至 \(\mathcal{O(n\log n)}\) 甚至 \(\mathcal{O(n)}\)。
- 决策单调性:设 \(p_i\) 表示 \(f_i\) 取到最小值时 \(j\) 的值(如果有多个 \(j\) 满足则取最小),即 \(f_i\) 的最优决策点。当代价函数 \(w\) 满足四边形不等式时,\(p_i\) 在 \([1,n]\) 上单调不降,\(f\) 具有决策单调性。则我们有
要证明这一点,可以使用反证法。假设对于 \(f_i,f_j(i < j)\),其最优决策点 \(p_j < p_i\),此时 \(p_j < p_i < i < j\),据四边形不等式有 $$w(p_j,j) + w(p_i,i) \ge w(p_j,i) + w(p_i,j)$$但是根据决策点的最优化条件又有 \(w(p_i,i) \le w(p_j,i),w(p_j,j) \le w(p_i,i)\),即 $$w(p_j,j) + w(p_i,i) \le w(p_j,i) + w(p_i,j)$$与四边形不等式矛盾。
由此得证。
对于 \(f_i\),其具有最小/最大最优决策点,将上述对 \(p_i\) 的定义更换为取最大后,关于原 \(p_i\) 的所有结论都是同样成立的,最大最优决策点同样具有单调不降的性质。注意可能存在 \(i < i'\),但是 \(i'\) 的最大最优决策点小于 \(i'\) 的最小最优决策点,故一般题目当中我们都默认只取最小(大)最优决策点来转移。
1.2 解题套路
通常我们先写出 \(f_i\) 的转移式子,大多数情况下,通常使用
\[w(j,i + 1) + w(j + 1,i) \ge w(j,i) + w(j + 1,i + 1) \]来检验代价函数是否满足四边形不等式。
然后对于一个决策,取它作为最优决策点的 \(f_i\) 所组成的是一个区间。对于决策 \(p_i < p_{i'}\),则这两种决策能成为最优决策的区间 \([l_{p_i},r_{p_i}],[l_{p_{i'}},r_{p_{i'}}]\),有 \(r_{p_i} < l_{p_{i'}}\)。
我们写一个二分函数 \(check(j,i)\) 计算出第一个以 \(j\) 作为最优决策不如以 \(i\) 作为最优决策优秀的点,那么可以使用单调队列来维护最优决策点,并进行 DP 转移了。
标签:le,不等式,决策,DP,四边形,最优,优化,单调 From: https://www.cnblogs.com/songszh/p/18518524/juecedandiaoxingDP