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

roger_yrj · 2023-07-27 13:43:09 · 个人记录

引入

四边形不等式

如果对于任意 a\le b\le c\le d，均有 f_{a,c}+f_{b,d}\le f_{a,d}+f_{b,c} 成立（相交优于包含），则称函数 f 满足四边形不等式

基本概念

决策单调性，顾名思义就是决策点具有一定的单调性。设 p_i 为 i 的最优决策点，那么对于 \forall 1\le i\le j\le n,p_i\le p_j。

由于决策单调性，对于每一个决策点 i，都有一个区间 [l_i,r_i) 或空集，使得 j\in [l_i,r_i),p_j=i。任意两个区间不会有交集（因为一个点只会有一个最优决策点）。

我们可以这么理解：对于一个决策点 i，如果存在这个 [l_i,r_i) 区间，那么就相当于在DP到 l_i 这个点时，这个决策点就超过了其他的决策点，成为最优决策点，到达它的巅峰期。在DP到 r_i 这个点时，这个决策点就被某个决策点超过了，结束了巅峰期，从此一蹶不振，再也无法成为最优决策点。

当一个决策点 i 刚到达巅峰期时就被某个点超过了，即 l_i=r_i，那么区间为空，这个决策点自然没有用了。

四边形不等式与决策单调性DP的关系

对于 \forall i\le j，假设分别是从 x,y 转移过来的，那么如果DP满足决策单调性的话，x\le y。

如果 x>y，由于 x,y 分别是 i,j 的最优决策点，那么一定有 dp_x+w_{x,i}\le dp_y+w_{y,i},dp_y+w_{y,j}\le dp_x+w_{x,j}。

如果 dp_x+w_{x,i}=dp_y+w_{y,i},dp_y+w_{y,j}=dp_x+w_{x,j} 的话，直接交换。

否则：

dp_x+w_{x,i}\le dp_y+w_{y,i},dp_y+w_{y,j}\le dp_x+w_{x,j}

w_{x,i}-w_{y,i}\le dp_y-dp_x,dp_y-dp_x\le w_{x,j}-w_{y,j}

w_{x,i}-w_{y,i}\le w_{x,j}-w_{y,j}

w_{x,i}+w_{y,j}\le w_{x,j}+w_{y,i}

不符合四边形不等式。注意这里 y\le x。

所以当函数 w 满足四边形不等式时，DP决策满足单调性。

优化方法

单调队列

我们把决策点放入单调队列中。设 f_{i,j} 为DP到 i，取到决策点 j 时代价是多少；q 为单调队列，t 为单调队列队尾，h 为队首。

当插入一个新的决策点时，依次进行以下操作。

判断队尾有没有用。如果队尾没有用，那么弹出队尾。因为 l_t 是 q_t 的巅峰期的开始，如果在 l_t 时 i 已经超越了 q_t，即 f_{l_t,q_t}\le f_{l_t,i}，那么 q_t 就不是最优决策点，那么 q_t 就没有巅峰期了，所以就没有用了。
计算 r_t，也就是计算 l_i（本质是一个东西）。
插入 i。此时 q_t=i。
判断队首有没有用。如果队首没有用，那么弹出队首。由于是从小到大枚举 i，所以当队首的巅峰期已过，即 r_h\le i，那么队首从此再也无法成为最优决策点，那么队首就没有用了。
计算 dp_i=f_{i,q_h}。因为队首现在处于巅峰期（因为如果不在巅峰期就被弹出了）。

时间复杂度 O(n^2)\rightarrow O(n\log n)

分治

先挖个坑，以后再来探索。

例题

Lightning Conductor
Yet Another Minimization Problem