[AHOI2017初中组] alter
题目描述
有 $n$ 盏灯排成一列,其中有些灯开着,有些灯关着。小可可希望灯是错落有致的,他定义一列灯的状态的不优美度为这些灯中最长的连续的开着或关着的灯的个数。小可可最多可以按开关 $k$ 次,每次操作可以使该盏灯的状态取反:原来开着的就关着,反之开着。现在给出这些灯的状态,求操作后最小的不优美度。
输入输出格式
输入格式
第一行两个整数 $n,k$。
第二行是一个长度为 $n$ 的字符串,其中有两种字符:`N` 和 `F`。其中 `N` 表示该灯开着,`F` 表示该灯关着。
输出格式
最小的不优美度。
输入输出样例
输入样例 #1
8 1
NNNFFNNN
输出样例 #1
3
说明
$30\%$ 的数据:$1\le k \le n\le20$;
$50\%$ 的数据:$1\le k \le n\le300$;
另有 $15\%$ 的数据:$1\le k \le n\le 10^5$,字符串为全 `N` 或全 `F`;
$100\%$ 的数据:$1\le k \le n\le 10^5$。
本题已经加入 hack 数据。