101403: [AtCoder]ABC140 D - Face Produces Unhappiness

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $400$ points

Problem Statement

There are $N$ people standing in a queue from west to east.

Given is a string $S$ of length $N$ representing the directions of the people. The $i$-th person from the west is facing west if the $i$-th character of $S$ is L, and east if that character of $S$ is R.

A person is happy if the person in front of him/her is facing the same direction. If no person is standing in front of a person, however, he/she is not happy.

You can perform the following operation any number of times between $0$ and $K$ (inclusive):

Operation: Choose integers $l$ and $r$ such that $1 \leq l \leq r \leq N$, and rotate by $180$ degrees the part of the queue: the $l$-th, $(l+1)$-th, $...$, $r$-th persons. That is, for each $i = 0, 1, ..., r-l$, the $(l + i)$-th person from the west will stand the $(r - i)$-th from the west after the operation, facing east if he/she is facing west now, and vice versa.

What is the maximum possible number of happy people you can have?

Constraints

  • $N$ is an integer satisfying $1 \leq N \leq 10^5$.
  • $K$ is an integer satisfying $1 \leq K \leq 10^5$.
  • $|S| = N$
  • Each character of $S$ is L or R.

Input

Input is given from Standard Input in the following format:

$N$ $K$
$S$

Output

Print the maximum possible number of happy people after at most $K$ operations.


Sample Input 1

6 1
LRLRRL

Sample Output 1

3

If we choose $(l, r) = (2, 5)$, we have LLLRLL, where the $2$-nd, $3$-rd, and $6$-th persons from the west are happy.


Sample Input 2

13 3
LRRLRLRRLRLLR

Sample Output 2

9

Sample Input 3

10 1
LLLLLRRRRR

Sample Output 3

9

Sample Input 4

9 2
RRRLRLRLL

Sample Output 4

7

Input

题意翻译

### 题目描述 有 $N$ 个人从东向西排成一排,每个人的状态用一个字符串 $S$ 表示,第i个字符 $s_i$ 表示从西边数起第 $i$ 个人的朝向```L``` 表示面朝西, ```R``` 表示面朝东。 对于队伍中的每个人,如果自己面前的人的朝向和自己一样,那么这个人就会感到幸福。如果面前的人朝向和自己不一样,或者面前没有人,这个人就感到不幸福。 你可以进行以下操作最多 $K$ 次(也可以一次都不进行): 选择整数$l,r(1≤l≤r≤N)$,让从西边数起第 $l,l+1,⋯,r$ 个人转身180度。 经过最多 $K$ 次操作后,感到幸福的人最多有多少人? ### 输入格式 第1行,2个正整数 $N,K$。 第2行,一个字符串 $S$ 。 ### 输出格式 一行一个正数表示答案

加入题单

上一题 下一题 算法标签: