← 返回题目列表

AtCoder · awc0082_c

C. 列车重新安排

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥正在进行列车重新安排工作。

最初,火车包括 A 红色 (R) 前面有车,后面跟着 B 蓝色 (B)汽车在他们后面连接。换句话说,将初始状态表示为一个字符串,它是一个长度为 N = A + B 其中 A 字符 R 之后是 B 字符 B.

Takahashi 可以执行以下操作零次或多次:

  • 选择一个整数 k (1 \leq k \leq N - 1)。拆下最后一个 k 当前列车的车厢。也就是把火车分成前面 N - k 汽车和后方 k 汽车。
  • 插入分离的后部 k 汽车作为一个整体,保持其顺序,进入前面的任何位置 N - k 汽车并重新连接它们。可能的插入位置为:车头之前、车尾之后或任意两辆相邻车厢之间,总共 N - k + 1 可能的位置。

每个操作都是针对该点列车的当前状态执行的。

给你一个字符串 T 长度 N 代表汽车的目标排列。求将初始状态转变为排列所需的最少操作数 T.

但是,如果 R 中的字符 T 不是 A (即汽车的组成与初始状态不同),不可能实现目标排列。在这种情况下,输出 -1.

约束

  • 1 \leq A
  • 1 \leq B
  • A + B \leq 10^7
  • T 是一个长度为 A + B 仅包含 R 和 B
  • 数量 R 中的字符 T 不一定 A

输入

A B
T
  • 第一行包含整数 A 和 B 代表红车和蓝车的数量,中间用空格隔开。
  • 第二行包含字符串 T 代表汽车的目标排列。

输出

输出将初始状态转变为所需的最少操作数 T。如果不可能,则输出 -1.


示例输入 1

2 2
RBBR

示例输出 1

1

示例输入 2

3 2
RRBBB

示例输出 2

-1

示例输入 3

7 6
RBRBBRRBRRBBR

示例输出 3

4

示例输入 4

25 20
BBBBBBBBBBBBBBBBBBBBRRRRRRRRRRRRRRRRRRRRRRRRR

示例输出 4

1

示例输入 5

1 1
RB

示例输出 5

0