/ Vijos / 题库 /

看球的巴士

看球的巴士

描述

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

格式

输入格式

第一行是整数N和D,1<=N<=2500,1<=D<=N。

接下来的N行,按排队的顺序,描述每个人支持的球队,用H或J表示。

输出格式

至少要几辆巴士。

样例1

样例输入1

14 3
H
J
H
H
H
J
H
J
H
H
H
H
H
H

样例输出1

2

限制

1 second

提示

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

来源

SQ

信息

ID
1331
难度
5
分类
动态规划 点击显示
标签
(无)
递交数
1320
已通过
484
通过率
37%
被复制
4
上传者

相关

在下列训练计划中:

RP++分类题库