Face Produces Unhappiness

题目描述

有 $N$ 个人从西向东排成一队。 给定一个长度为 $N$ 的字符串 $S$ 表示这些人的朝向。 从西边数起第 $i$ 个人如果 $S$ 的第 $i$ 个字符为 $L$ 则面向西，为 $R$ 则面向东。 如果某人前面的人（即更靠东的人）面向与其相同的方向，则该人是快乐的。 但是如果某人前面没有其他人站着，则他/她不算快乐。 你可以执行以下操作任意次，次数在 $0$ 到 $K$（含）之间： 操作：选择整数 $l$ 和 $r$ 满足 $1 \leq l \leq r \leq N$，将队列的第 $l$ 到第 $r$ 人整体旋转 $180$ 度：即对于每个 $i = 0, 1, ..., r-l$，从西边数第 $(l + i)$ 个人将在操作后站在从西边数第 $(r - i)$ 的位置，并且如果他/她当前面向西则在操作后面向东，反之亦然。 最多可以得到多少个快乐的人？

输入格式

输入从标准输入给出，格式如下： $N$ $K$ $S$

输出格式

输出在最多 $K$ 次操作后可以得到的最大快乐人数。

6 1
LRLRRL

3

13 3
LRRLRLRRLRLLR

9

10 1
LLLLLRRRRR

9

9 2
RRRLRLRLL

7

提示

$N$ 是满足 $1 \leq N \leq 10^5$ 的整数。 $K$ 是满足 $1 \leq K \leq 10^5$ 的整数。 $|S| = N$ $S$ 的每个字符都是 $L$ 或 $R$。如果我们选择 $(l, r) = (2, 5)$，得到 $LLLRLL$，此时从西边数第 $2$、$3$ 和 $6$ 个人是快乐的。

标签: AtCoder|abc140D

来源

AtCoder|abc140D