分数: 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