[USACO23DEC] Target Practice S

Luogu

IDLGP9979

Time1000ms

Memory256MB

DifficultyP4

模拟USACO2023O2优化分类讨论

Bessie 是一只仿生牛。在一条数轴上，她正尝试命中 $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 开枪。如果有一个靶子在 Bessies 当前的位置，这个靶子将被命中并摧毁。它不可以再次被命中。如果在 Bessie 开始前，你被允许修改序列中的至多一条命令，Bessie 最多可以命中多少靶子？ ## Input 第一行包含 $T$ 和 $C$。下一行包含 $T$ 个靶子的位置，均为 $[-C,C]$ 范围内的不同整数。下一行包含长度为 $C$ 的命令序列，仅包含字符 `F`、`L` 和 `R`. ## Output 输出修改至多一个命令后，Bessie 可以命中的靶子的最大数量。 [samples] ## Note ### 样例解释 1 如果你对命令序列不做任何修改，Bessie 将命中两个靶子。 | 命令 | 位置 | 命中的靶子数目 | | :----------- | :----------- | :----------- | | Start | 0 | 0 | | L | -1 | 0 | | F | -1 | 1 | | F | -1 | 1（无法摧毁靶子超过 1 次） | | R | 0 | 1 | | F | 0 | 2 | | R | 1 | 2 | | R | 2 | 2 | 如果你将最后一条命令由 `R` 修改为 `F`，Bessie 将命中三个靶子： | 命令 | 位置 | 命中的靶子数目 | | :----------- | :----------- | :----------- | | Start | 0 | 0 | | L | -1 | 0 | | F | -1 | 1 | | F | -1 | 1（无法摧毁靶子超过 1 次） | | R | 0 | 1 | | F | 0 | 2 | | R | 1 | 2 | | F | 1 | 3 | ### 样例解释 2 如果命令序列不修改，在位置 $0$ 的唯一一个靶子将被命中。由于一个靶子不能被多次摧毁，答案为 $1$。 ### 测试点性质 - 测试点 $4-6$ 满足 $T,C \le 1000$。 - 测试点 $7-15$ 没有额外限制。

Samples

Input #1

3 7
0 -1 1
LFFRFRR

Output #1

Input #2

1 5
0
FFFFF

Output #2

Input #3

5 6
1 2 3 4 5
FFRFRF

Output #3

API Response (JSON)

{
  "problem": {
    "name": "[USACO23DEC] Target Practice S",
    "description": {
      "content": "Bessie 是一只仿生牛。在一条数轴上，她正尝试命中 $T$（$1 \\leq T \\leq 10^5$）个位于不同位置的靶子。Bessie 在位置 $0$ 开始行动，并遵循一个长度为 $C$（$1 \\leq C \\leq 10^5$）的命令序列，序列由 `L`、`F` 和 `R` 组成： - `L`：Bessie 向左移动一个单位距离。 - `R`：Bessie 向右移动一个单位距离。 - `",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9979"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Bessie 是一只仿生牛。在一条数轴上，她正尝试命中 $T$（$1 \\leq T \\leq 10^5$）个位于不同位置的靶子。Bessie 在位置 $0$ 开始行动，并遵循一个长度为 $C$（$1 \\leq C \\leq 10^5$）的命令序列，序列由 `L`、`F` 和 `R` 组成：\n\n- `L`：Bessie 向左移动一个单位距离。\n- `R`：Bessie 向右移动一个单位距离。\n- `...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments