A16541 | $Maximum Color Segment$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

给你一根长度为 $n$ 的绳子，每个单位长度都被涂成红色或黑色。绳子可用一个长度为 $n$ 的字符串表示，字符 R（红色）和 B（黑色）。还给你两个整数 $m$ 和 $k$。 你可以最多进行 $m$ 次（也可以一次不做）如下操作： - 任选长度恰好为 $k$ 的一段连续子串。 - 将子串内每个单位的颜色反转：R 变为 B，B 变为 R。 例如，考虑绳子 RRRRBRRR，$k=4$。如果你选择第 $3$ 个到第 $6$ 个字符（RRRRBRRR），经过一次反转后，绳子变为 RRBBRBRR。 定义“颜色段数”为：将绳子划分为若干连续的段，每段均由同一种颜色组成，且段数最少。例如，RRBRRRBB 的颜色段数为 $4$：RR、B、RRR、BB。 你的任务是，在至多 $m$ 次操作后，求能够得到的颜色段数的最大值。 $^{\ast}$一个字符串 $t$ 是字符串 $s$ 的子串，当且仅当能通过从 $s$ 的首部和尾部分别删除若干（可以为零或全部）字符后得到 $t$。

第一行包含三个整数 $n$、$m$ 和 $k$，分别表示绳子的长度、最多可操作次数和每次操作的反转区间长度。 第二行包含一个长度为 $n$ 的，仅由 R 和 B 组成的字符串，表示初始的绳子内容。 - $1 \leq n \leq 3000$ - $0 \leq m \leq 3000$ - $1 \leq k \leq n$

输出一个整数，表示最多进行 $m$ 次操作后，绳子的最大颜色段数。

输入 #1

5 4 3
RRBRR

输出 #1

C++ 编辑器

输入

输出