Redistricting

题目描述

奶牛超级城市 Bovinopolis 正在重新划分选区！——这在居住于此的两大奶牛品种（荷斯坦牛 Holsteins 与更赛牛 Guernseys）之间一直是一个充满争议的政治过程，因为两者都希望确保自己在 Bovinopolis 政府中保有足够的影响力。 Bovinopolis 的大都会区域由一条直线上的 $N$ 个牧场组成（$1 \leq N \leq 3 \cdot 10^5$），每个牧场里有且仅有一头奶牛，品种要么是 Holstein，要么是 Guernsey。 Bovinopolis 政府希望将整个大都会区域划分为若干个连续的选区，使得每个选区包含的牧场数不超过 $K$（$1 \leq K \leq N$），并且每个牧场恰好属于一个选区。由于政府目前由 Holsteins 掌控，他们希望找到一种重新划分方式，使得 Guernsey 占多数或平局的选区数量尽可能少（当一个选区内 Guernsey 数量等于 Holstein 数量时，称为平局）。 一个关心此事的 Guernseys 联盟试图估算政府重新划分选区可能造成的损害。请帮助他们计算：在最坏情况下，“Guernsey 占多数或平局”的选区数量的最小值会是多少。

输入格式

第一行包含两个用空格分隔的整数 $N$ 和 $K$。 第二行包含一个长度为 $N$ 的字符串。每个字符为 'H' 或 'G'，分别表示 Holstein 或 Guernsey。

输出格式

请输出使“Guernsey 占多数或平局”的选区数量最少时，该最小可能数量。

7 2
HGHGGHG

3

提示

题目来源：Dhruv Rohatgi

标签: USACO|2019|Platinum

来源

USACO|2019|Platinum