A6964 | 净化传输信号
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
通信卫星接收到了一串长度为 $N$ 的原始信号字符串
经过初步分析,我们识别出了其中包含的一段核心指令字符串
为了优化存储空间,系统标记了一组“冗余下标”
你可以对
1. 每次操作可以删除
2. 删除操作后,剩余的字符串必须仍然包含
3. 操作不改变字符在原始字符串中的相对下标判定(即下标是固定的,不会因为前面的字符被删除了而改变后续字符的下标索引)。
请问:在保证
source。经过初步分析,我们识别出了其中包含的一段核心指令字符串
pattern(pattern 保证是 source 的子序列)。为了优化存储空间,系统标记了一组“冗余下标”
targetIndices。你可以对
source 进行“清理操作”:1. 每次操作可以删除
source 中下标位于 targetIndices 中的任意一个字符。2. 删除操作后,剩余的字符串必须仍然包含
pattern 作为其子序列(字符顺序不变)。3. 操作不改变字符在原始字符串中的相对下标判定(即下标是固定的,不会因为前面的字符被删除了而改变后续字符的下标索引)。
请问:在保证
pattern 完整性的前提下,你**最多**可以执行多少次删除操作?输入格式
输入共三部分:
1. 第一行包含一个字符串
2. 第二行包含一个字符串
3. 第三行包含一个整数 $K$,表示可删除下标数组的长度。
4. 第四行包含 $K$ 个整数,表示
1. 第一行包含一个字符串
source。2. 第二行包含一个字符串
pattern。3. 第三行包含一个整数 $K$,表示可删除下标数组的长度。
4. 第四行包含 $K$ 个整数,表示
targetIndices 的元素,保证按升序排列且互不相同。输出格式
输出一个整数,表示最多可以删除的字符数量。
输入输出样例
输入 #1
abbaa aba 3 0 1 2
输出 #1
1
输入 #2
bcda d 2 0 3
输出 #2
2
## 样例解释
**样例 #1 解释:**
-
- 假如删除下标 0 ('a'),剩余 "bbaa",包含 "aba"(子序列),操作合法。
- 假如删除下标 1 ('b'),剩余 "abaa",包含 "aba",操作合法。
- 假如删除下标 2 ('b'),剩余 "abaa",包含 "aba",操作合法。
- 但如果你试图同时删除下标 0 和 1(变为 "baa"),则不再包含 "aba"。
- 最多只能删 1 个。
**样例 #2 解释:**
- 删除下标 0 ('b') 和下标 3 ('a')。
- 剩余 "cd",其中 "d" 是
- 删除了 2 个字符,这是最大值。
## 数据范围
- $1 \le N \le 3000$ (
- $1 \le M \le N$ (
-
- 保证
**数据点分布:**
- 测试点 1-5:$N \le 20$
- 测试点 6-15:$N \le 500$
- 测试点 16-25:$N \le 3000$
**样例 #1 解释:**
-
source = "abbaa", pattern = "aba", 可删下标 = {0, 1, 2}。- 假如删除下标 0 ('a'),剩余 "bbaa",包含 "aba"(子序列),操作合法。
- 假如删除下标 1 ('b'),剩余 "abaa",包含 "aba",操作合法。
- 假如删除下标 2 ('b'),剩余 "abaa",包含 "aba",操作合法。
- 但如果你试图同时删除下标 0 和 1(变为 "baa"),则不再包含 "aba"。
- 最多只能删 1 个。
**样例 #2 解释:**
- 删除下标 0 ('b') 和下标 3 ('a')。
- 剩余 "cd",其中 "d" 是
pattern "d" 的子序列。- 删除了 2 个字符,这是最大值。
## 数据范围
- $1 \le N \le 3000$ (
source 长度)- $1 \le M \le N$ (
pattern 长度)-
targetIndices 中的元素在 $[0, N-1]$ 范围内。- 保证
pattern 是 source 的子序列。**数据点分布:**
- 测试点 1-5:$N \le 20$
- 测试点 6-15:$N \le 500$
- 测试点 16-25:$N \le 3000$
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?