Target Practice

题目描述

Bessie 是一头机器牛（robovine），也被称为 cowborg。她在数轴上尝试射击一系列 $T$ 个 $(1 \leq T \leq 10^5)$ 靶子，这些靶子位于互不相同的位置上。Bessie 从位置 $0$ 开始，并按照一个由 $C$ 条 $(1 \leq C \leq 10^5)$ 指令组成的字符串行动，每条指令为 L、F 或 R 之一： L：Bessie 向左移动一个单位。 R：Bessie 向右移动一个单位。 F：Bessie 开火。如果在 Bessie 当前所在位置有靶子，则该靶子被命中并摧毁，且不能再次被命中。 如果你允许在 Bessie 开始执行之前，将字符串中的至多一条指令改为另一种不同的指令，那么 Bessie 最多能命中多少个靶子？

输入格式

第一行包含 $T$ 和 $C$。 第二行包含 $T$ 个靶子的位置，它们是互不相同的整数，范围在 $[-C,C]$。 第三行包含长度为 $C$ 的指令字符串，只包含字符 F、L 和 R。

输出格式

输出在将指令字符串中至多一条指令修改后，Bessie 能命中的靶子数量的最大值。

3 7
0 -1 1
LFFRFRR

3

1 5
0
FFFFF

1

5 6
1 2 3 4 5
FFRFRF

3

提示

如果你不对字符串做任何修改，Bessie 将命中两个靶子： Command | Position | Total Targets Hit --------+----------+------------------- Start | 0 | 0 L | -1 | 0 F | -1 | 1 F | -1 | 1 (不能摧毁同一个靶子超过一次) R | 0 | 1 F | 0 | 2 R | 1 | 2 R | 2 | 2 如果你把最后一条指令从 R 改为 F，Bessie 将命中全部三个靶子： Command | Position | Total Targets Hit --------+----------+------------------- Start | 0 | 0 L | -1 | 0 F | -1 | 1 F | -1 | 1 (不能摧毁同一个靶子超过一次) R | 0 | 1 F | 0 | 2 R | 1 | 2 F | 1 | 3 如果指令保持不变，位于 0 的唯一靶子会被摧毁。 由于一个靶子不能被多次摧毁，答案为 1。 SCORING: Inputs 4-6: $T,C \le 1000$ Inputs 7-15: 无额外限制。 题目鸣谢：Suhas Nagar

标签: USACO|2023|Silver

来源

USACO|2023|Silver