P9870 [NOIP2023] 双序列拓展——dp转二维网格问题

· · 个人记录

注：本篇题解分析了为什么只会出现横线竖线和L型

初见思路 dp

约束条件就相当于扩展后的序列任意两项的大小关系必须一样，而条件可以直接从第一项的关系中看出来

那么就可以钦定 a 中所有元素 >b 了（若 a_1>b_1 交换即可）

发现这个问题可以看作令一个序列的一个元素与另一个序列的一段区间匹配，要求 a 中选中所有元素必须 <b 中所有元素，然后是否存在匹配方案的问题

因为后续匹配之和目前两个序列匹配过的位置有关，就可以得到一个dp

令 f(i,j) 为 a 最后一位匹配到 i , b 最后一位匹配到j的方案是否存在

当枚举到一位时，有三种选择

再加上之前的限制，就有

f(i,j)=[a_i>b_j]\;and\;(f(i-1,j-1)\;or\;f(i-1,j)\;or\;f(i,j-1))

在网格上的进一步分析

把dp状态画到平面上，发现事实上就是查询 (0,0) 到 (n,m) 的连通性，其中 a_i\le b_j 的点 (i,j) 是障碍

考虑障碍的结构，从生成角度考虑

于是当起点/终点被两方面围住时,一定会形成一个L型

也就是说只有四种情况

前两个的判断是简单的，那么对于第三个，可以描述为

\exist (i,j),\forall k\le i,a_k\le b_j \; and \;\forall l\le j,a_i\le b_l

这里的两个 \forall 可以转化成最值，那么就变成了

a_{max[1,i]}\le b_j \;and\;a_i\le b_{min[1,j]}

到这里已经有一个二分的想法了，枚举i后尽量找最大的 b_j ,同时满足 a_i\le b_{min[1,j]}，前缀最值满足单调性，可以二分出可以选的 j 的区间取最值

注意到当 i 逐渐变大时，前缀最大值会单调递增，就需要越来越往后的 j ，那么对于比之前小的 a_i ，就不需要调整 j 的位置而可以直接跳过，此时 j 的位置应当是单调递增的，使用双指针维护即可

对于第四个，两条序列reverse一下就好了