四边形不等式优化

Vision271 · 2022-07-22 20:10:15 · 个人记录

概述

• 还没想好概述啥，总之就是像上刑。

四边形不等式

引入

• 我们先来看一张图。

• 在如图所示的四边形中（左半边，右半边是辅助线），我们有：a+b\leqslant c+d。

• 证明不难，只要将 d 平移如图然后把 a 拉下来，那么 c,d,a+b 就构成了一个三角形。当且仅当四边形不存在（也即三角形不存在）时该不等式取等。

• 将其四边形的几何形态抽去（可以认为就是放在一个数轴上），感性理解一下，我们有：

  (l,r)+(l',r')\leqslant (l,r')+(l',r)

• 即，“区间和小于区间并加区间交”，或，“交叉小于包含”

  • 逻辑上讲，根据题目要求是 \min/\max，不等号方向可以取反。

  • 但事实上，只有 \min 能用，理由的话...下面证明 DP 满足四边形不等式那里，在 l'=r 的时候有一步非常关键的操作是把 c 放大了，这一放大依赖着 \leqslant 的不等号方向。

  • 我暂时没有想到能绕过这点然后证明 DP 满足四边形不等式的办法。既然 DP 都不满足，后面的更是无从谈起，没法优化了。

四边形不等式与区间包含单调性

• 四边形不等式：对于函数 f(l,r)(l\leqslant r)，如果总有 f(l,r)+f(l',r')\leqslant f(l,r')+f(l',r)(l\leqslant l'\leqslant r\leqslant r')，那么它满足四边形不等式。

• 区间包含单调性：对于函数 f(l,r)(l\leqslant r)，如果总有 f(l',r')\leqslant f(l,r)(l\leqslant l'\leqslant r'\leqslant r)，则它满足区间包含单调性。

• 这有什么用呢？

2D1D 型区间动态规划的优化

• 考虑如下的转移方程（典型代表如链上的石子合并）：\mathit{dp}_ {l,r}=\min_{k=l}^r(\mathit{dp}_ {l,k}+\mathit{dp}_ {k+1,r}+\mathit{c}_ {l,r})。

• 显而易见暴力转移是 O(n^3) 的，但我们可以考虑利用 c 的一些性质来优化它。

• 定理 1：如果 c 满足四边形不等式和区间包含单调性，那么 dp 满足四边形不等式，即，dp_{l,r}+dp_{l',r'}\leqslant dp_{l,r'}+dp_{l',r}。

  • 使用数学归纳法。

  • 首先我们很容易看到，当 l=l' 或 r=r'，四边形不等式显然成立（式左右全同了）。

  • 考虑模仿区间 dp，顺着 length（len 表示当前考虑的长度，更具体地说，表示 r'-l+1） 进行归纳。

  • 从而从上面的结论我们可以推出 length=1 时，dp 满足四边形不等式。

  • 首先我们约定，\mathit{k}_ {l,r}(l\leqslant r) 表示 \mathit{dp}_ {l,r} 对应的最优转移点，即 \mathit{dp}_ {l,r}=\mathit{dp}_ {l,\mathit{k}_ {l,r}}+\mathit{dp}_ {\mathit{k}_ {l,r}+1,r}+\mathit{c}_ {l,r}。

  • 接下来使用归纳法。假设对于 length=1,2,\dots,len-1，dp 都满足四边形不等式，试证对于 length=len 也成立：

    • 当 l=l' 或 r=r'：见前。

    • 当 l<l'=r<r'，即欲证 dp_{l,r}+dp_{r,r'}\leqslant dp_{l,r'}+dp_{r,r}：依赖 c 的区间包含单调性。

      • 若 k_{l,r'}<r（这里记为 k），即 dp_{l,r'} 的最优转移点 <r：拆开第一项。

        • 显然我们有 dp_{l,r}\leqslant dp_{l,k}+dp_{k+1,r}+c_{l,r}。

        • 利用归纳假设，因为 k+1>l 即 length(k+1,r')<length(l,r')，我们有 dp_{k+1,r}+dp_{r,r'}\leqslant dp_{k+1,r'}+dp_{r,r}（注意这个式子和 dp 本身的转移完全没关系（那个的话，式左的两个应该是连续而又不重叠的），纯粹是我们配凑所用）。

        • 两式相加，消去相同部分，我们得到 dp_{l,r}+dp_{r,r'}\leqslant dp_{l,k}+c_{l,r}+dp_{k+1,r'}+dp_{r,r}。

        • 由 k 的定义（此处 k=k_{l,r'}），我们有 dp_{l,r'}=dp_{l,k}+dp_{k+1,r'}+c_{l,r'}。由 c 满足区间包含单调性，c_{l,r}\leqslant c_{l,r'}。

        • 联立两式代入前式得：dp_{l,r}+dp_{r,r'}\leqslant dp_{l,r'}+dp_{r,r}。

      • 若 k_{l,r'}\geqslant r：拆开第二项。

        • 由归纳（k+1\leqslant r'），dp_{l,r}+dp_{r,k}\leqslant dp_{l,k}+dp_{r,r}。

        • 加合，dp_{r,r'}+dp_{l,r}\leqslant dp_{l,k}+dp_{k+1,r'}+c_{r,r'}+dp_{r,r}

        • 由 k 的定义及 c_{r,r'}\leqslant c_{l,r'}，合并式右前三项，得：dp_{l,r}+dp_{r,r'}\leqslant dp_{l,r'}+dp_{r,r}。

    • 当 l<l'<r<r'，即欲证 dp_{l,r}+dp_{l',r'}\leqslant dp_{l,r'}+dp_{l',r}：

      • 我们约定，k=k_{l,r'},k'=k_{l',r}。容易看出，有k< r',k'< r。

      • 那么其实接下来的就是对位拆然后基于归纳假设拼回来。

      • 若 k\leqslant k'(s.t.(such\ that)\ l\leqslant k\leqslant k'(through\ this)<r,l'\leqslant k'< r)：第一项用 k 拆，第二项用 k' 拆。

        • 由 c 满足四边形不等式，我们有 c_{l,r}+c_{l',r'}\leqslant c_{l,r'}+c_{l',r}。

        • 由归纳假设，我们有 dp_{k+1,r}+dp_{k'+1,r'}\leqslant dp_{k+1,r'}+dp_{k'+1,r}。

        • 两个合并代入（其实可以一步化完但那样可读性太差）：dp_{l,r}+dp_{l',r'}\leqslant dp_{l,k}+dp_{k_+1,r'}+c_{l,r'}\ +\ dp_{l',k'}+dp_{k'+1,r}+c_{l',r}。

        • 前后三项分别合并，得到 dp_{l,r}+dp_{l',r'}\leqslant dp_{l,r'}+dp_{l',r}。

      • 若 k'\leqslant k(s.t.\ l'\leqslant k'<r,l'\leqslant (through\ this)k'\leqslant k<r')：第一项用 k' 拆，第二项用 k 拆。

        • 代入得 dp_{l,r}+dp_{l',r'}\leqslant dp_{l,k}+dp_{k+1,r'}+c_{l,r'}\ +\ dp_{l',k'}+dp_{k'+1,r}+c_{l',r}。

        • 合并！收工！dp_{l,r}+dp_{l',r'}\leqslant dp_{l,r'}+dp_{l',r}。

• 定理 2：如果 dp_{l,r} 满足四边形不等式，那么 k_{l,r} 满足如下的单调性：k_{l,r-1}\leqslant k_{l,r}\leqslant k_{l+1,r}(l+1<r)。

  • 感性理解一下就是，当把 l 或 r 右移时，总有 k_{l,r} 单调不降。

  • 使用反证法。我们将三者分别记为 k_1,k,k_2。

    • 当 k_1>k，即 l<k+1<k_1+1\leqslant r-1<r：

      • 由 k 定义，有 dp_{l,k}+dp_{k+1,r}\leqslant dp_{l,k_1}+dp_{k_1+1,r}（c 消去）。

      • 由 dp 满足四边形不等式，我们有 dp_{k+1,r-1}+dp_{k_1+1,r}\leqslant dp_{k+1,r}+dp_{k_1+1,r-1}。

      • 加合，得 dp_{l,k}+dp_{k+1,r-1}\leqslant dp_{l,k_1}+dp_{k_1+1,r-1}。

      • 给式左右都加上 c_{l,r-1}，观察实际含义：对于 dp_{l,r-1}，k 比 k_1 更优。这与 k_1 是其最优转移点矛盾，所以不成立，一定有 k_1\leqslant k。

    • 当 k_2<k，即 l<l+1\leqslant k_2<k< r。

      • 加合，dp_{l+1,k}+dp_{k+1,r}\leqslant dp_{l+1,k_2}+dp_{k_2+1,r}。

      • 同上，不符合 k_2 定义。

  • 综上，k_{l,r-1}\leqslant k_{l,r}\leqslant k_{l+1,r}(l+1<r) 得证。

  • 之所以要求 l+1<r，是因为我们每种情况的第二行都是在用 dp 的四边形不等式。这个东西要成立，必须有 l\leqslant l'\leqslant r\leqslant r'，在这里其实就是依赖“当”后面的“即”。但如果 l+1\geqslant r，容易发现那里的连不等式不成立，或者某个 k 掉出范围了。

实现原理

• 在 dp 时记录 k_{l,r}，从而对于 dp_{l,r}，枚举时的范围由 l\sim r 降为了 k_{l,r-1}\sim k_{l+1,r}。

• 则总复杂度为 \sum\limits_{1\leqslant l<r\leqslant n} k_{l+1,r}-k_{l,r-1}+1。

• 仔细观察这个式子，手推画图可以发现对于每个 k_{l,r}，它只有在计算 dp_{l,r+1} 时作为 k_{l,r-1} 被减去和在计算 dp_{l-1,r} 时作为 k_{l+1,r} 被加上，即，只用两次，而且是一次加一次减。

  • 则不妨将 1 提出，k 总量为 n^2，则 1 的贡献是 n^2 级别的。

  • 稍微裂项相消一下，可以发现只有形如 k_{x,n} 的 k 只会被加而不会被减，类似地，只有形如 k_{1,x} 的 k 只会被减而不会被加，从而上式可以化为 \sum\limits_{i=1}^nk_{i,n}-k_{1,i}。

  • 忽略后项，则 k 贡献的复杂度上界也是 n^2。

• 综上所述，经过四边形不等式优化的该种 dp 的复杂度为 O(n^2)。常数其实也比较优秀，2 倍大概算是小常数了。

2D1D 型分层动态规划的优化

• 考虑如下的转移方程（典型代表如广义多重背包）：dp_{i,j}=\max_{k=lim}^j(dp_{i-1,k}+v_{i,k,j})。

• 朴素 dp O(nm^2)（状态 n\times m，转移 O(m)）。

• 一看这个 v_i 就知道 O(nm) 不可做（i\leqslant n,j\leqslant m），毕竟跨层的 v 都不满足四边形不等式，搁这搁这呢。

• 但对于同一层的转移，在同层的 v 满足四边形不等式的前提下（这里取 \max 所以是大于等于号，交叉大于包含），我们可以来玩一些 trick。

• 先放结论：k_{i,j}\leqslant k_{i,j+1}（等效转移则 k 取最大）。

  • 直接起手反证法。考虑一组 l<l'\leqslant r<r',s.t.\ k_{i+1,r}=l',k_{i+1,r'}=l。

  • 按定义拆一下，我们有 dp_{i+1,r}=dp_{i,l'}+v_{i+1,l',r},dp_{i+1,r'}=dp_{i,l}+v_{i+1,l,r'}。

  • 由 v_{i+1} 满足四边形不等式， v_{i+1,l',r}+v_{i+1,l,r'}\leqslant v_{i+1,l,r}+v_{i+1,l',r'}。

  • 加合并代入，有 dp_{i+1,r}+dp_{i+1,r'}\leqslant dp_{i,l'}+v_{i+1,l',r'}\ +\ dp_{i,l}+v_{i+1,l,r}<dp_{i+1,r}+dp_{i+1,r'}。

  • 则显然式右的两个 k 不劣于原来假设的 k，所以不成立。

• 这等价于 k_j\in [k_{j-1},k_{j+1}]，但这没有实际意义，因为 dp_i 的拓扑序同级，试图都卡上下界会有环，即为了转移 dp_j 需要 k_{j-1}，反之亦然。

• 之所以区间型可做，是因为其上下界都在拓扑序更早的区间上，而这里同层点之间在拓扑序上同级，试图都卡上下界显然有环，故试图模仿区间型把复杂度降到 O(nm) 是痴人说梦。

• 不过我们可以分治优化：

  • 先求最中间的 k_{i,mid}，然后左右递归求解。

  • 考虑使用类似整体二分的方法：记转移来源区间为 [fl,fr]，转移目标区间为 [l,r]，每次考察 [l,r] 的中点 mid，遍历 [fl,fr] 找到其转移点 fmid，于是有 k_{j<mid}\leqslant fmid\leqslant k_{j>mid}。

  • 故可以递归 ([l,mid-1],[fl,fmid]) 和 ([mid+1,r],[fmid,fr])。不妨将之视为把转移来源放到了转移目标的二分树上，则在认为 [fmid,fr] 为 (fmid,fr] 时显然有每个转移来源只在一条满链上出现，fmid 加回来也就是全树多一个点，总转移量 O((len+flen)\log len)=O(len\log len)。

• 类似地，我们可以二分栈。我还不会所以先咕着，只谈一下大体思路：

  • 对于转移来源点 j，记 tow_j 为受其转移的区间的右界，于是在 (tow_{j-1},r] 上二分，不断判断 j 和 j+1 这两者作为转移来源谁更优，于是得到每个转移来源的“管辖区间”。

  • 总转移量 O(len\log len+len)=O(len\log len)。

1D1D 型动态规划的优化

• 考虑如下的转移方程（典型代表如啥我也不清楚）：dp_i=\max_{j=lim}^{i-1}(dp_j+c_{j,i})。

• 直接视作上面那种的不分层来做就好了啦。我不想写了。因为太像所以两者共用一个例题啦，都在下面。

广义多重背包

• 题意：有 n 组物品，每组物品有相同的 c 或相同的 v（两者只有一者相同），求在 \sum c\leqslant lim 前提下的 \max\sum v。

• 我们以 c 相同为例。首先有一个显然的事实：同组内一定先选 v 小的，后选 v 大的。

• 换言之，该问题相当于一个分组背包问题，每个集合内的元素形如选该组的前 k 个。

• 那么写一下式子：dp_{i,j}=\max_{k\leqslant j}(dp_{i-1,k}+v_{i,k,j})。这是一般的 2D1D 的形式，更特化一点的话可以写成 dp_{i,j}=\max_{k\times c_i\leqslant j}(dp_{i-1,j-k\times c_i}+v_{i,k})。

• 那么，我们有 k_j\leqslant k_{j+1}，这里 k 为最优转移来源。证明的话...上面就是，所以不再写一遍了。

• 于是可以做到 O(n\sum c\log) 的复杂度，非常优秀。

CF868F Yet Another Minimization Problem

• 题意略。本题为 2D1D 的状态，但转移系数与层无关，转移式为 dp_{i,j}=\min_{k<j}(dp_{i-1,k}+c_{k+1,j})。

• 本题的 c 满足交叉小于包含的四边形不等式，证明可以考虑反证法：

  • 假设有交叉大于包含，不妨记为 l<l'\leqslant r<r'，相当于 c_{l,r}+c_{l',r'}>c_{l,r'}+c_{l',r}。

  • 容易证明其满足区间包含单调性，于是必然有 c_{l,r'}\geqslant c_{l,r},c_{l',r'}>c_{l',r}，因为第二个不等号取等时，以 c_{l,r}=c_{l',r} 为例，有 c_{l,r}+c_{l',r'}>c_{l,r'}+c_{l',r}=c_{l,r'}+c_{l,r}\to c_{l',r'}>c_{l,r'}，显然不成立。

  • 考虑 c_{l,r},c_{l',r'}>c_{l',r} 的实际意义，即两者的新增都构成了新的匹配，换言之，a_l,a_r' 都在 [l',r] 中出现过。

  • 首先考虑 a_l\neq a_r'，发现此时显然有 c_{l,r'}-c_{l',r}=c_{l,r}-c_{l',r}+c_{l',r'}-c_{l',r}，于是 c_{l,r}+c_{l',r'}=c_{l,r'}+c_{l',r}，与假设矛盾。

  • 则一定有 a_l=a_r'，不妨设其在 [l',r] 中出现了 k 次，则 c_{l,r}-c_{l',r}=c_{l',r'}-c_{l',r}=k，但 c_{l,r'}-c_{l',r}=k+k+1，即 c_{l,r'}-c_{l',r}>c_{l,r}-c_{l',r}+c_{l',r'}-c_{l',r}，于是 c_{l,r}+c_{l',r'}>c_{l,r'}+c_{l',r}，仍然与前设矛盾。

  • 所以一定有交叉不大于包含。

• 那么这很板，但是注意到一个问题：没法转移。c 怎么算？全算出来就 T 了。

• 考虑模仿莫队，直接暴力！对每个区间，莫队的移动量显然是 flen；到左儿子的移动量是 fr-fmid，再回来一样，到右儿子是 fmid-fl，再回来还是一样，于是该区间的莫队总移动量为 O(flen)。

• 考虑到整棵二分树的转移来源长度之和也就只有 O((len+flen)\log)=O(n\log)，事实上莫队的总移动量也就是这个级别的。

• 当然也可以改 bfs 实现，每层 O(n) 地一起算完。总复杂度都是 O(kn\log n)。