四边形不等式优化 DP

First Post:

Last Update:

Word Count:
992

Read Time:
3 min

Page View: loading...

引入（DP 形式）

在最优化 DP 中，常见如下形式的 DP 转移方程

四边形不等式用于证明以上的转移方程具有性质“决策单调性”。

这里的 操作应该被理解为一个广义上取“最优化”的操作。

四边形不等式

对于任意 ，若函数 满足

则称函数 满足“四边形不等式”。

简单来说，就是“相交优于包含”。

顺便，显然若 满足四边形不等式，则 也满足四边形不等式，因此我们在下文中不妨将 式简写为

四边形不等式可以理解为在合理的定义域内， 的二阶混合差分 非正。

因此四边形不等式也可以理解为函数凸性。

决策单调性

在式 中，记 为最小的最优决策点，即 是令 取最小的、最小的 。

四边形不等式是决策单调性的一个充分不必要条件。

Proof

若存在下标 使得 ，又因为 ，因此有

根据假设，有

因此

与四边形不等式矛盾。

基于决策单调性，有两种主流方法可以将 DP 优化到 。

分治

假如 与先前计算的 无关，则可以利用这个方法。另外对于一些二维 DP 的转移，如

则可以对 转移时应用分治，可以将复杂度从 优化到 。

具体来说，我们定义过程 计算 到 的值，并且根据决策单调性已知其最优决策点在区间 内。

则 可以实现为：

  1. 令 ，从 枚举决策点计算 ，记录其最优决策点为 ；
  2. 计算 ；
  3. 计算 。

容易得到过程的时间复杂度为 。

一般来说，解决全局问题需要调用 ，故时间复杂度是 。

Trick：类莫队转移贡献

存在一个很强的结论，就是即使代价函数 不好算，但是可以快速移动端点，那么复杂度仍然是 的。

分析一下端点移动的操作数就证完了。

单调队列 + 二分

在 计算不能离线时使用。

在双端队列中维护有序三元组 ，表示 为 的当前最优决策点。

  • 初始时将 插入队列；
  • 从 枚举点 ，顺便计算 ：
    • 检查队头的三元组，令 ，若此时 ，那这个元组已经没用了，将它从队头弹出；
    • 从队头取当前最优决策点转移 ；
    • 将决策点 插入队尾，具体地，
      • 若队尾的决策点 在 处劣于 ，根据决策单调性，这整个元组没用了，将他从队尾弹出；
      • 若队尾的决策点 在 处优于 而在 处劣于 ，那我们二分这个点 使得 处 较劣而 处 较优；
      • 将队尾的 ，将 插入队尾。

单调队列的均摊是 的，而二分的复杂度是 ，总的复杂度为 。

Trick：计算代替二分

有时可以直接计算决策的“反超点”，从而做到震撼人心的 求解。

SOLUTION

看到限制是全局的，不妨将其拆成两部分，先只考虑 的部分，再反过来求一遍，最后取最大值。

因此显然有

这个东西做法很多，利用 的值最多会有 ，可以做到 的复杂度。

每个点的转移是完全独立的，因此也可以使用分治法做，复杂度是 的。

但是，如果我们使用队列二分的方法，可以将复杂度优化到线性。

假设当前要把决策点 插入单调队列，此时队尾的决策点为 ，我们希望计算得到一个最小的 ，使得 点为最小的 优于 的转移点。

即解不等式

移项得

由于 ，因此不等式左侧为正数，设 ，显然 时无解。

若 ，有

因此

至此，我们可以 计算决策点插入的位置，因此总的时间复杂度为 的。

≡