专栏文章

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

lli_cat
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min69krc
此快照首次捕获于
2025/12/01 21:15
3 个月前
此快照最后确认于
2025/12/01 21:15
3 个月前
查看原文
注：本篇题解分析了为什么只会出现横线竖线和L型

初见思路 dp

约束条件就相当于扩展后的序列任意两项的大小关系必须一样，而条件可以直接从第一项的关系中看出来
那么就可以钦定 aa 中所有元素 >b>b 了（若 a1>b1a_1>b_1 交换即可）
发现这个问题可以看作令一个序列的一个元素与另一个序列的一段区间匹配，要求 aa 中选中所有元素必须 <b<b 中所有元素，然后是否存在匹配方案的问题
因为后续匹配之和目前两个序列匹配过的位置有关，就可以得到一个dp
令 f(i,j)f(i,j) 为 aa 最后一位匹配到 ii , bb 最后一位匹配到j的方案是否存在
当枚举到一位时，有三种选择
  • 这两位形成一个新的匹配，从 f(i−1,j−1)f(i-1,j-1) 转移而来
  • ii 加入 jj 所匹配出的区间里，从 f(i−1,j)f(i-1,j) 转移来
  • jj 加入 ii 所匹配出的区间里，从 f(j,i−1)f(j,i-1) 转移来
再加上之前的限制，就有 f(i,j)=[ai>bj]  and  (f(i−1,j−1)  or  f(i−1,j)  or  f(i,j−1))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)(0,0) 到 (n,m)(n,m) 的连通性，其中 ai≤bja_i\le b_j 的点 (i,j)(i,j) 是障碍
考虑障碍的结构，从生成角度考虑
  • aia_i 从小到大考虑,生成一行/列   ⟹  \implies 每行障碍状态必然只有包含关系
  • bib_i 从大到小考虑,生成一列/行   ⟹  \implies 每列障碍状态必然只有包含关系
于是当起点/终点被两方面围住时,一定会形成一个L型
也就是说只有四种情况
  • 贯穿的横线
  • 贯穿的竖线
  • 起点被L型包住
  • 终点被L型包住
前两个的判断是简单的，那么对于第三个，可以描述为 ∃(i,j),∀k≤i,ak≤bj  and  ∀l≤j,ai≤bl\exist (i,j),\forall k\le i,a_k\le b_j \; and \;\forall l\le j,a_i\le b_l
这里的两个 ∀\forall 可以转化成最值，那么就变成了 amax[1,i]≤bj  and  ai≤bmin[1,j]a_{max[1,i]}\le b_j \;and\;a_i\le b_{min[1,j]}
到这里已经有一个二分的想法了，枚举i后尽量找最大的 bjb_j ,同时满足 ai≤bmin[1,j]a_i\le b_{min[1,j]}，前缀最值满足单调性，可以二分出可以选的 jj 的区间取最值
注意到当 ii 逐渐变大时，前缀最大值会单调递增，就需要越来越往后的 jj ，那么对于比之前小的 aia_i ，就不需要调整 jj 的位置而可以直接跳过，此时 jj 的位置应当是单调递增的，使用双指针维护即可
对于第四个，两条序列reverse一下就好了

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...