四边形不等式优化

“满足四边形不等式”是“满足决策单调性”的充分不必要条件，满足决策单调性的题目不一定可以使用这篇文章提到的优化方式。

解决的问题

对于转移方程为类似于下面情况的且 \(n\le 2\times 10^5\)，那么可以考虑用四边形不等式优化。

\[f_{i}=\min\limits_{j=0}^i\{V(j,i)\} \]

具体的 \(V(j,i)\) 需要满足一些性质并且可以 \(O(1)\) 求解。

考虑怎么最后 \(f_i\) 实际上取到的 \(j\) 就是 \(f_i\) 的决策点，我们记其为 \(p_i\)。

四边形不等式

定义

如果 \(\forall a,b,c,d\in[1,n]\cap \mathbb{Z}^+\wedge a\lt b\le c\lt d\) 满足 \(V(a,d)+V(b,c)\ge V(a,c)+V(b,d)\)，那么我们称 \(V\) 满足四边形不等式。

这个结论看起来不好记，实际上也很难懂，可以简记为包含关系大于相交关系。

推论

如果 \(\forall a,c\in[1,n]\cap\mathbb{Z}^+\wedge a\lt c\) 满足 \(V(a,c+1)+V(a+1,c)\ge V(a,c)+V(a+1,c+1)\)，那么也可以推出 \(V\) 满足四边形不等式。

证明

令 \(a'\gets a+1\) 得到：

\[V(a+1,c+1)+V(a+2,c)\ge V(a+1,c)+V(a+2,c+1) \]

把两式相加整理得到：

\[V(a,c+1)+V(a+2,c)\ge V(a,c)+V(a+2,c+1) \]

考虑一直重复上面的操作就可以把 \(b=a+1\) 一直推广到 \(b=+\infty\)。

考虑通过类似的方法拓展 \(c\)，容易理解。

应用

四边形不等式的证明及其的麻烦，考试的是否可以直接通过暴力枚举 \(a,c\) 来确定是否满足四边形不等式。

直接枚举 \(2\) 个元素比去枚举 \(4\) 个元素要优秀许多。

决策单调性

定义

如果 \(\forall i,j\in[1,n]\cap\mathbb{Z}^+\wedge i\le j\) 满足 \(p_i\le p_j\)，那么我们称这个转移方程具有决策单调性。

定理

如果 \(V\) 满足四边形不等式，那么这个转移方程满足决策单调性。

证明

设 \(i,j\in[1,n]\cap\mathbb{Z}^+\wedge i\le j\)，如果 \(p_i\gt p_j\) 那么就有：

\[f_i=V(p_i,i),f_{j}=V(p_j,j) \]

根据定义有：

\[V(p_i,i)+V(p_j,j)\ge V(p_i,j)+V(p_j,i) \]

所以至少有一个 \(f\) 是优于本来的，欲假设矛盾，因而得证。

决策单调性优化 DP

1

分治

如果 \(V(j,i)\) 的计算与 \(f_j\) 无关，那么可以考虑使用分治算法解决。 ^1fabba

这样的转移方程很少，一般都是题目要求求出 \(1\) 到 \(n\) 之内所有的答案。

考虑设计函数 \(\text{solve}(l,r,x,y)\) 表示求解 \([l,r]\) 的 \(f\) 的值，而且其决策都是再 \([x,y]\) 中的。

计算 \(f_{mid}\) 的值，假设其决策点再 \(P\)，那么显然对于 \([l,mid)\) 的 \(f\) 的决策点都在 \([x,P]\)，而对于 \((mid,r]\) 的决策点则是在 \([P,y]\) 里。

一直递归直到 \(l=r\)，时间复杂度为 \(O(n\log n)\)。

单调栈与队列

先假设所有的决策点都是 \(0\)，那么从前向后计算，尝试将在计算出 \(f_i\) 之后将 \(i\) 作为决策点。

因为其具有决策单调性，所以按照上面的方式进行更新，如果 \(f_i\) 可以更新到 \(f_x\)，那么从 \(f_x\) 到 \(f_n\) 都是可以被 \(f_i\) 更新的。

发现这个东西具有单调性，那么考虑去二分第一个满足用 \(f_i\) 更新更有的节点。

在二分出第一个位置假设是 \(p\)，那么考虑把 \([p,n]\) 合并为一个区间，表示这个区间的决策点都是 \(i\)。

时间复杂度是 \(O(n\log n)\)，\(\log\) 是二分。

因为一次操作最多只会新增一个区间，所以总共清除的区间数最大只有 \(n\)，就是 \(O(n)\) 的。