DP 优化——决策单调性优化

决策单调性优化

决策单调性定义

对于 \(dp_i\)，若 \(dp_i\) 由 \(dp_j\) 转移最优，则 \(j\) 即为 \(dp_i\) 的最优决策点。

在状态转移方程 \(dp_i=min\{dp_j+w(j,i)\}^*\)，\(j\in[0,i)\) 中，设 \(p_i\) 为 \(dp_i\) 的最优决策点，若 \(p\) 在 \([1,n]\) 上单调不减，则称 \(dp\) 具有决策单调性

\(*\)：\(w(a,b)\) 是定义在整数集合上的二元函数，下同。

四边形不等式

定义

若函数 \(w(x,y)\) 满足对于 \(\forall a,b,c,d\in\mathbb Z\)，\(a\le b\le c\le d\)，都有 \(w(a,d)+w(b,c)\ge w(a,c)+w(b,d)\)，则称函数 \(w(x,y)\) 满足四边形不等式。

推论

若函数 \(w(x,y)\) 满足对于 \(\forall a,b\in\mathbb Z\)，\(a\le b\)，都有 \(w(a+1,b)+w(a,b+1)\ge w(a,b)+w(a+1,b+1)\)，则称函数 \(w(x,y)\) 满足四边形不等式。

证明

对于 \(a<c\)，有 \(w(a,c+1)+w(a+1,c)\ge w(a,c)+w(a+1,c+1)\)；

对于 \(a+1<c\)，有 \(w(a+1,c+1)+w(a+2,c)\ge w(a+1,c)+w(a+2,c+1)\)；

两式相加，整理得 \(w(a,c+1)+w(a+2,c)\ge w(a,c)+w(a+2,c+1)\)；

以此类推，对于任意的 \(a\le b\le c\)，有 \(w(a,c+1)+w(b,c)\ge w(a,c)+w(b,c+1)\)；

同理，对任意的\(a\le b\le c\le d\)，有 \(w(a,d)+w(b,c)\ge w(a,c)+w(b,d)\)。

决策单调性与四边形不等式

定理

在状态转移方程 \(dp_i=min\{dp_j+w(j,i)\}\)，\(j\in[0,i)\) 中，若函数 \(w\) 满足四边形不等式，则 \(dp\) 具有决策单调性。

证明

定义 \(p_i\) 表示 \(i\) 的最优决策点。

\(\forall i\in[1,n],\forall j\in[0,p_i−1]\)，根据 \(p_i\) 为 \(i\) 的最优决策点，则有

\[dp_{p_i}+w(p_i,i)\le dp_j+w(j,i) \]

\(\forall i'\in[i+1,n]\)，因为 \(w\) 满足四边形不等式，则有

\[w(j,i′)+w(p_i,i)\ge w(j,i)+w(p_i,i′) \]

移项，可得

\[w(p_i,i′)−w(p_i,i)\le w(j,i′)−w(j,i) \]

与第一个不等式相加，可得

\[dp_{p_i}+w(p_i,i′)≤dp_j+w(j,i′) \]

即 \(i′\) 的最优决策点一定大于等于 \(p_i\)。故 \(dp\) 具有决策单调性。