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

tanghg

4个月前发布

四边形不等式

对于函数 \(w(x,y)\)，如果对于所有的 \(a\leq b \leq c \leq d\) 都满足

\[w(a,c)+w(b,d)\leq w(a,d)+w(b,c) \]

则称其满足四边形不等式。还有一种等效写法对于 \(l<r-1\) 有

\[w(l,r-1)+w(l+1,r)\leq w(l,r)+w(l+1,r-1) \]

则同样满足。

\[w(l,r-1)-w(l,r)\leq w(l+1,r-1)-w(l+1,r) \]

\[-\Delta w_l(r)\leq -\Delta w_{l+1}(r)\leq\cdots \]

\[w(a,c)-w(a,d)\leq w(b,c)-w(b,d) \]

\[\sum_{i=c+1}^d -\Delta w_a(i)\leq \sum_{i=c+1}^d -\Delta w_b(i) \]

发现可以转化。同时有第二种归纳证明：
对于 \(a=b\) 或 \(c=d\) 的情况显然成立。
若 \(b-a+d-c=2\) 则 \(a\leq a+1\leq d-1\leq d\) 成立。
若 \(b-a+d-c>2\)，则必有 \(b-a\) 或 \(d-c\) 有一项大于等于 \(2\)，即求证

\[w(b-1,c)+w(b,d)\leq w(b-1,d)+w(b,c) \]

为 \(b-1\leq b\leq c\leq d\) 的归纳结果证毕。

四边形不等式有一些性质

\(w_1,w_2\) 满足四边形不等式，有常数 \(c_1,c_2\leq 0\)，则 \(c_1w_1+c_2w_2\) 同样满足四边形不等式。
对于任意函数 \(f,g\)，函数 \(w(i,j)=f(i)-g(j)\) 必然满足四边形不等式。
对于一个凸函数 \(h\)，如果 \(w\) 满足区间包含性和四边形不等式，那么 \(w^{‘}(i,j)=h(w(i,j))\) 也满足四边形不等式。

区间包含性指对于 \(a\leq b\leq c\leq d\)，有 \(w(a,d)\geq w(b,c)\)。

决策单调性

对于函数 \(f(i)\)，令 \(\text{opt(i)}\) 表示所有能让 \(f(i)\) 取到最值的 \(j\) 的集合，之后通常只考虑 \(\text{opt(i)}\) 的最值即可。令 \(p_i=\max \text{opt(i)}\)（当然最小值也可以）称为最优决策点。

离线情况

对于函数

\[f(i)=\min_{1\leq j\leq i}\{ w(j,i)\} \]

有决策单调性

\[i<j\Rightarrow p_i\leq p_j \]

若 \(i<j\)，\(p_i>p_j\)

\[p_j<p_i\leq i<j \]

\[w(p_i,j)\leq w(p_j,i) \]

\[w(p_j,j)<w(p_i,j) \]

相加发现不满足四边形不等式。

具体实现可以分治求解每一次 \(s(l,r,q_l,q_r)\) 可以得到 \(m=\frac{l+r}{2}\) 的 \(f_m,p_m\)。向下递归就递归 \(s(l,m,q_l,p_m),s(m+1,r,p_m,q_r)\)。

在线情况

\[f(i)= \min_{0\leq j<i}\{ f(j)+w(j,i)\} \]

同样满足决策单调性。实现方法是二分队列。维护三元组队列 \((l,r,i)\) 表示 \(p_j=i,j\in [l,r]\)。若用 \(f(i)\) 来更新。首先如果用 \(f(i)\) 更新更佳的就直接弹出。直到对于 \((l_1,r_1,i_1)\) 有 \(f(i)+w(i,l_1)>f(i_1)+w(i_1,l_1)\)。

若 \(f(i)+w(i,r_1)>f(i_1)+w(i_1,r_1)\) 那么就直接添加 \((r_1+1,n,i)\)。否则二分出一个 \(k\)，将区间分割成 \((l_1,k,i),(k+1,n,i)\) 即可。

区间情况

\[f(k,i)=\min _{1\leq j\leq i}\{f(j,k)+f(k+1,i)+w(j,i)\} \]

有决策单调性 \(i<j\) 时

\(p_{k,i}\leq p_{k,j}\)
\(p_{k-1,i}\leq p_{k,i}\leq p_{k,i+1}\)
下对 \(2\) 证明：

f(k-1,i) 表示将 \([1,i]\) 分成 \(k-1\) 个区间的最有分化，那么令

\[g(t,x)=\min_{x\leq j\leq i}\{g(t-1,j+1)+w(x,j)\} \]

表示将 \([x,i]\) 分成 \(t\) 个子区间的最优分化。

\[g:p^g_{t,x}\leq p^g_{t,y} \]

后可推出一一对应从而证明。

还有结论是 \(f_k\) 满足凸性，所以可以使用王钦石二分来优化。