← 返回题目列表

Codeforces · 2172/L

L. 最大颜色段

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

给你一根绳子 $$$n$$$ 个单位长,每个单位都涂成红色或黑色。绳子可以表示为由字符组成的长度为 $$$n$$$ 的字符串 R (红色)和 B (黑色)。您还获得两个整数 $$$m$$$ 和 $$$k$$$。

您可以执行以下操作 最多 $$$m$$$ 次(可能为零次):

  • 选择长度恰好为 $$$k$$$ 的绳子的任何连续子字符串$$$^{\text{*}}$$$。
  • 翻转子串中每个单元的颜色:each R 变为 B,以及每个 B 变为 R.

例如,考虑绳索 RRRRBRRR $$$k = 4$$$。如果您选择第 $$$3$$$ 到第 $$$6$$$ 个字符 (RRRRBRRR),那么翻转后,绳子就变成 RRBBRBRR.

定义 颜色段数 作为绳索可以分成的连续段的最小数量,以便每个段由单一颜色的单元组成。例如,绳子 RRBRRRBB 有 $$$4$$$ 颜色段: RR, B, RRR,和 BB.

您的任务是确定执行后颜色段的最大可能数量 最多 $$$m$$$ 操作。

$$$^{\text{*}}$$$ 字符串 $$$t$$$ 是字符串 $$$s$$$ 的子字符串,如果 $$$t$$$ 可以通过从 $$$s$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。

输入

第一行包含三个整数$$$n$$$、$$$m$$$和$$$k$$$,分别代表绳子的长度、允许的最大操作数以及每个操作的翻转窗口的长度。

第二行包含长度为 $$$n$$$ 的字符串,仅由字符组成 R 和 B,代表绳索的初始内容。

  • $$$1 \le n \le 3000$$$
  • $$$0 \le m \le 3000$$$
  • $$$1 \le k \le n$$$

输出

单行输出一个整数,表示最多执行$$$m$$$操作后可能出现的最大色段数。

示例

输入
复制

5 4 3
RRBRR

输出
复制

5

输入
复制

10 3 3
RRRRBBRRRB

输出
复制

8

输入
复制

7 4 7
RRBRBBR

输出
复制

5