← 返回题目列表

AtCoder · abc140_d

D. 面子产生不快乐

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

分数: 400 点

问题陈述

有 N 人们从西向东排队。

给定的是一个字符串 S 长度 N 代表人民的方向。 的 i- 从西边的第一个人面朝西,如果 i- 第一个字符 S is L,如果该字符为东 S is R.

如果一个人面前的人面向同一个方向,他/她就会感到幸福。 然而,如果没有人站在一个人面前,他/她就会不高兴。

您可以执行以下操作任意次数 0 和 K (含):

操作:选择整数 l 和 r 这样 1 \leq l \leq r \leq N,并旋转 180 度队列的部分: l-th, (l+1)-th, ..., r第人。也就是说,对于每个 i = 0, 1, ..., r-l, (l + i)- 第一个来自西方的人将站在 (r - i)- 操作后从西数第一个,如果他/她现在面向西,则面向东,反之亦然。

你最多可以拥有多少个快乐的人?

约束

  • N 是满足以下条件的整数 1 \leq N \leq 10^5.
  • K 是满足以下条件的整数 1 \leq K \leq 10^5.
  • |S| = N
  • 每个字符 S is L or R.

输入

输入由标准输入按以下格式给出:

N K
S

输出

打印最多之后快乐的人的最大数量 K 操作。


示例输入 1

6 1
LRLRRL

示例输出 1

3

如果我们选择 (l, r) = (2, 5),我们有 LLLRLL,其中 2-nd, 3-rd,和 6第一个西方人很高兴。


示例输入 2

13 3
LRRLRLRRLRLLR

示例输出 2

9

示例输入 3

10 1
LLLLLRRRRR

示例输出 3

9

示例输入 4

9 2
RRRLRLRLL

示例输出 4

7