问题 3551 --看球的巴士

3551: 看球的巴士

题目描述

  两个球队的支持者要一起坐车去看球,他们已经排成了一列。我们要让他们分乘若干辆巴士,同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突,希望两队的支持者人数尽量相等,差至多是D。有一个例外,就是一辆车上的人全部都是一个球队的支持者。问要将这N个人全部送至球场,至少要几辆巴士。

输入

第一行是整数N和D,1< =N< =2500,1< =D< =N。
接下来的N行,按排队的顺序,描述每个人支持的球队,用H或J表示。

输出

至少要几辆巴士。

样例输入输出

输入#1 复制
14 3
H
J
H
H
H
J
H
J
H
H
H
H
H
H
输出#1 复制
2

提示

有多种方案,例如让前9人做一辆车,差正好是3;后5人做一辆车,因为只有一对的支持者。

序号 标题 作者 发表时间 费用 订购数 操作