四边形不等式相关-程序员充电站

四边形不等式

我们称一个二元函数\(w(i, j)\)满足四边形不等式，当且仅当对于任意\(a \le b \le c \le d\)满足：

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

即交叉小于包含。

其可以用来对转移进行优化，具体的，设：

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

定义\(\operatorname{opt}(i)\)表示计算\(f(i)\)时最优的那个决策点\(j\)，称其满足决策单调性当且仅当对于任意\(i < j\)满足\(\operatorname{opt}(i) \le \operatorname{opt}(j)\)。

性质\(1\)：

若\(w(i, j)\)满足四边形不等式，则\(f(i)\)满足决策单调性。

考虑反证法，若存在\(i < j\)且\(x = \operatorname{opt}(i) > y = \operatorname{opt}(j)\)，那么根据定义有\(w(x, j) \ge w(y, j), w(y, i) \ge w(x, i)\)，于是\(w(x, j) + w(y, i) \ge w(y, j) + w(x, i)\)，违反了四边形不等式，于是得证。

性质\(2\)：

如果对于任意\(i, j\)满足\(w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)\)，那么\(w\)满足四边形不等式。

证明比较显然，考虑\(w(i + 1, j) + w(i, j + 1) - w(i, j) - w(i + 1, j + 1) \ge 0\)，这表示\(w\)的二维差分矩阵非负；于是考察其二维差分矩阵上一个子矩阵\((b + 1, d + 1), (a, c)\)的和必然也非负，即\(w(a, d) - w(a, c) - w(b, d) + w(b, c) \ge 0\)，这是四边形不等式的定义。

上面那个决策单调性太特殊了，只对\(f(i) = \min w(j, i)\)生效，感觉没有什么实际用途，一般都是这种问题：将序列分段使得权值最小，即：

\[f(i) = \min_{j \le i} f(j - 1) + w(j, i) \]

这种怎么办？考虑：

性质\(3\)：

若\(w(i, j)\)满足四边形不等式，则\(w(i, j) = x_i + y_j\)也满足。

这是显然的，带入进去把\(x, y\)都消掉了。

于是只需要\(w(i, j)\)满足四边形不等式，则上面\(f(i)\)的转移也满足决策单调性。

如果强制钦定了要分\(k\)段，可以根据情况使用 wqs 二分或者多加一维解决。

考虑\(w(l, r)\)可能是\(\sum_{l \le i \le j \le r} c(i, j)\)的形式：

性质\(4\)：

若\(c(i, j) \ge 0\)，则\(w(l, r) = \sum_{l \le i \le j \le r} c(i, j)\)满足四边形不等式。

考虑证明\(w(x, y) + w(x + 1, y + 1) \le w(x, y + 1) + w(x + 1, y)\)，考虑拆贡献\(x + 1 \le i \le j \le y\)的\((i, j)\)对两边贡献是相同的，然后左边是\(\sum_{i = x, j \in [x, y]} c_{i, j} + \sum_{i \in [x + 1, y + 1], j = y + 1} c_{i, j}\)，然后右边\(w(x, y + 1)\)去掉\(x + 1 \le i \le j \le y\)的\((i, j)\)后是\(\sum_{i = x,j \in [x, y + 1]} c(i, j) + \sum_{i \in [x, y + 1], j = y + 1} c(i, j)\)，于是右边多考虑了\(c(x, y + 1)\)，得证。

例题

P1880 [NOI1995] 石子合并

考虑区间 dp，定义\(dp(l, r)\)表示将区间\([l, r]\)合并的最小代价，于是有转移：

\[dp(l, r) = (s_r - s_{l - 1}) + \min\limits_{k = l}^{r - 1} (dp(l, k) + dp(k + 1, r)) \]

钦定\(l\)固定时，有\(w(i, j) = dp(l, i) + dp(i + 1, j)\)，考虑证明\(w(i, j)\)满足四边形不等式，你推下式子发现等价于证明\(dp(i, j)\)满足四边形不等式。

这里\(dp(i, j)\)满足四边形不等式的充要条件是\(h(i, j) = s_i - s_{j - 1}\)也满足四边形不等式且满足区间包含单调性，可以对长度数学归纳发得到。

然后你发现上面固定右端点\(r\)时也有决策单调性，于是有\(\operatorname{opt}(l, r) \in [\operatorname{opt}(l, r - 1), \operatorname{opt}(l + 1, r)]\)，所以这样枚举决策点时间复杂度就是\(O(n^2)\)的。

link

于是可以得到性质\(5\)：

设\(w(l, r)\)满足四边形不等式且满足区间包含单调性，若\(dp(l, r) = w(l, r) + \min\limits_{k = l}^{r - 1} (dp(l, k) + dp(k + 1, r))\)，那么\(dp(l, r)\)也满足四边形不等式；且固定\(l\)或者固定\(r\)时都满足决策单调性，即\(\operatorname{opt}(l, r) \in [\operatorname{opt}(l, r - 1), \operatorname{opt}(l + 1, r)]\)。

类似题目 UVA10304 Optimal Binary Search Tree。

CF868F Yet Another Minimization Problem

考虑\(c(i, j) = [a_i = a_j]\)，那么\(w(l, r) = \sum_{l \le i \le j \le r} c(i, j)\)满足四边形不等式，于是\(dp\)时：

\[dp_{i, j} = \min_{k \le i} dp_{k - 1, j - 1} + w(k, i) \]

这个最优决策\(k\)具有单调性；考虑用分治与整体二分的思想解决。

即我们定义\(solve(l, r, kl, kr)\)表示目前在转移\([l, r]\)内的点，其最优决策点在\([kl, kr]\)内；那么可以暴力算出\(mid\)的最优决策点\(kmid\)，然后递归到\(solve(l, mid - 1, kl, kmid), solvew(mid + 1, r, kmid, kr)\)；显然递归层数使用\(\log n\)层，且每层\([kl, kr]\)的总长度是\(O(n)\)级别的，于是单次时间复杂度是\(O(n \log n)\)。

现在问题在于如何快速算\(w(l, r)\)，你考虑用类似莫队的走指针方式解决，你发现每次移动的长度是\(O(len)\)级别的，于是最终是\(O(n \log n)\)次。

总时间复杂度为\(O(nk \log n)\)。

link

P3515 [POI 2011] Lightning Conductor

这题你推一下式子，若对于\(i\)的答案是\(k\)，那么要对于所有\(j\)满足：

\[k + h_i \ge h_j + \sqrt{|i - j|} \]

\[k \ge h_j + \sqrt{|i - j}| - h_i \]

于是：

\[k = \lceil\max_{j} h_j + \sqrt{|i - j|} \rceil - h_i \]

考虑怎么算\(h_j + \sqrt{|i - j|}\)，这里分讨\(j < i\)和\(j > i\)两种情况算就可以去掉绝对值，然后\(w(i, j) = \sqrt{i - j}\)，容易发现\(w\)满足四边形不等式，于是有决策单调性。

于是分治解决即可，时间复杂度为\(O(n \log n)\)。

link

P4767 [IOI 2000] 邮局加强版

显然对于每个设立的邮局，到其距离最近的村庄集合是集合，于是可以设立状态\(dp_{i, j}\)表示考虑前\(i\)个村庄放了\(j\)个邮局的最小代价：

\[dp_{i, j} = \min\limits_{k < i} dp_{k, j - 1} + w(k + 1, i) \]

其中\(w(l, r)\)表示在区间\([l, r]\)内放一个邮局的最小代价，显然将邮局放在中位数位置最优，于是可以增量递推：

\[w(l, r) = w(l, r - 1) + a_r - a_{\frac{l + r}{2}} \]

你发现\(w\)满足四边形不等式，于是我们按照\(j\)分层每层分治计算即可，时间复杂度为\(O(nk \log n)\).

link

这里证明一下上面的\(w\)满足四边形不等式，即\(w(i, j) + w(i + 1, j + 1) \le w(i, j + 1) + w(i + 1, j)\)；首先注意到\([i, j + 1]\)与\([i + 1, j]\)的中位数一样，设为\(k\)；
那么\(w(i, j + 1) = w(i + 1, j) + a_k - a_i + a_{j + 1} - a_k = w(i + 1, j) + a_{j + 1} - a_i\)，于是\(w(i, j + 1) + w(i + 1, j) = 2w(i + 1, j) + a_{j + 1} - a_i\)。
然后根据\(w\)的最小性的定义，可以得到\(w(i, j) \le w(i + 1, j) + a_k - a_i, w(i + 1, j + 1) \le w(i + 1, j) + a_{j + 1} - a_k\)，于是\(w(i, j) + w(i + 1, j + 1) \le 2w(i + 1, j) + a_{j + 1} - a_i = w(i, j + 1) + w(i + 1, j)\)得证。

P10861 [HBCPC2024] MACARON Likes Happy Endings

洛谷同步题解。

令\(s\)为前缀异或，那么\(c(i, j) = [s_j \oplus s_{i - 1} = d] \ge 0\)，于是\(w(l, r) = \sum_{l \le i \le j \le r}\)满足四边形不等式，于是\(dp\)时：

\[dp_{i, j} = \min_{k \le i} dp_{k - 1, j - 1} + w(k, i) \]

然后分治去做，计算\(w(k, i)\)可以简单走指针计算，于是时间复杂度是\(O(nk \log n)\)的。

link

四边形不等式相关