1 条题解
-
0
题目分析
清澈(transparent)题解
题意抽象出来是:定义两个序列 匹配当且仅当 。给定一个固定的序列 ,多次询问给定 问 中是否存在子序列与 匹配。
这题最关键的性质是, 中所有以第 个位置为结尾的与查询序列的某个前缀匹配的子序列里只需要保留最长的那个。或者说,如果存在合法子序列,那么一定存在一个合法子序列使得,以这个子序列里的每个位置为结尾拿出来的子序列都是以这个位置为结尾时最长的匹配。这个性质的证明有很多种方法,可以归纳证明,也可以分类讨论+调整法。
有了这个性质之后就可以 dp 了,对于每次询问,记询问序列为 ,记 表示以 为结尾的能与 的某个前缀匹配的子序列中最长的长度。现在已知 ,要求出 。记 $C(x,y)=\begin{cases}1&(x>y)\\0&(x=y)\\-1&(x<y)\end{cases}$ 那么 会对 产生贡献当且仅当 。对 按 或 分类,每一类里的转移与最长上升子序列(LIS)的转移是本质相同的。直接枚举的复杂度为 ,用二分则可以优化至 。总时间复杂度为 。
- 1
信息
- ID
- 159
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 5
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者