决策单调性优化 DP 学习笔记

MortisM · 2022-11-22 10:50:54 · 个人记录

声明：全文讨论 \min 及 w(a,d)+w(b,c)\ge w(a,c)+w(b,d) 等情况，具体应用请自行更换 \le, \ge 符号。

四边形不等式

设 w(i,j) 为定义在整数域上的二元函数，若对于任意 a\le b\le c\le d 都满足 w(a,d)+w(b,c)\ge w(a,c)+w(b,d) (即 交叉 \le 包含），则称 w 满足 四边形不等式。

定理：w 同上。若满足对于所有 a<b，都有 w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1)，则 w 满足四边形不等式。

证明： 懒得证了咕咕咕。会用就行，感性理解一下就是对的吧。

决策单调性

最优化 DP 就是说每一个状态只能由一个最优的状态转移来，那么我们称这个最优的状态为 最优决策点。

决策单调性 就是说当 DP 顺次进行时（本质就是一个 DAG），最优决策点单调变化（单调 不降）。

假设有转移方程 f_i=\min(f_{j}+w(j,i))（构造出来具体的问题还挺容易的？），如果 w 没有任何性质的话那肯定只能暴力 DP，但是如果 w 满足上面所讲的四边形不等式呢？

猜想此时 f 满足决策单调性（事实确实如此）。用反证法，设 p_i 表示 f_i 的最优转移点，假设 f 没有决策单调性，即存在 x<y 且 p_x>p_y。

根据最优决策点的定义可知：

因为 w 有四边形不等式性质，所以对于 p_y<p_x<x<y 可知：

上下两式大大小小同时相加可得：

即：

显然，这与 p_x 的最优性矛盾，故假设不成立，即 f 具有 决策单调性。

这样四边形不等式的定理作用就体现出来了，它可以帮助我们证明 w 函数的四边形不等式性质，具体判断方法见例题。

应用 & 技巧

前面讲过了，设 p_i 表示 f_i 的最优决策点，那么 p_i 单调不降，下面是处理决策单调性题目的两种方法（感觉 Sol.2 比 Sol.1 好写不止一点点）。

Sol. 1：单调队列

用单调队列维护 p。

当求出一个 f_i 时，检查 i 可以作为哪些 j 的最优决策点（i<j），就是要维护这样一个东西（借用一下 @Flash_Hu 的图）：

具体来说，就是一些三元组 (l,r,j) 表示 p[l\sim r] 的最优决策点都是 j，这个东西用单调队列维护，具体操作如下：

• 插入 i。
  • 取出队尾元素 (l_t,r_t,j_t)。
  • 若对于 r_t 来说 i 更好就直接干掉这个元素，并回到上一步操作；否则停止。
  • 若当前队列无元素，插入 i，停止。
  • 否则而分出 i 第一次比 j_t 好的位置，记为 x。改 r_t 为 x-1，新插入 i（这里 l=x）。
• 不停干掉堆头没有用的元素。
• 更新答案。

时间复杂度 \mathcal{O}(n\log n)。

Sol. 2 分治

非常好算法，英雄联盟，爱来自瓷器（真的非常非常好写）。

假设我们知道对于 a[l\sim r] 的最优决策点在 [L,R] 范围内。设 m=\lfloor\frac{l+r}{2}\rfloor，a[l\sim m] 的最优决策点为 p。那么 a[m+1\sim R] 的最优决策点肯定在 [p,R] 中。

分治搞定，时间复杂度 \mathcal{O}(n\log n)。

例题

P3515 [POI2011]Lightning Conductor

推式子，p\geq a_j-a_i+\sqrt{|i-j|}。设 f_i=\max{a_j+\sqrt{|i-j|}}，答案为 f_i-a_i。因为绝对值不好搞，序列正反做两次取最大值即可去掉绝对值。

剩下板子了。Sol. 1 的代码。Sol. 2 的代码。

P4767 [IOI2000]邮局

先排序。设 f_{i,j} 表示前 i 个位置放 j 个邮局的最小代价，w(i,j) 表示 i\sim j 放一个邮局最小值。转移：