BZPRO
#3367. [Usaco2004 Feb]The Big Game 球赛
内存限制:128 MiB
时间限制:10 Sec
提交
提交记录
讨论
题目描述
快到奶牛冠军杯足球赛了,今年在J队与H队之间将会出现十分激烈的对抗.
作为今年牛奶生产创记录的奖励,约翰同意他的奶牛们观看这场比赛.N(1≤N≤2500)头
牛已经在仓房排好队.他们将被挨个儿地接上车,直到约翰喊停.之后下一辆车继续挨个儿接奶牛.最终,奶牛将都被送上车.一些牛是J队的球迷,另一些是H队的球迷,竞争对手之间往往相处得很糟.所以,约翰不能让一辆汽车上载过多的J队球迷或H队球迷,这样另一支队的球迷在途中会受到恐吓.因此,他得保证一辆车中,两队球迷的个数差的绝对值在I(1≤I≤N)内.除非那辆车上只有J队或H队的球
迷.
给出奶牛上车的次序,请计算出最少几辆汽车可以解决问题.
输入格式
第1行输入两个分开的整数N和J;接下来N行表示奶牛们在仓房中排队的顺序.用J和H表示
她们是J队和H队昀球迷.
输出格式
一个整数,表示最少汽车的数量.
样例
样例输入
14 3
H
J
H
H
H
J
H
J
H
H
H
H
H
H
样例输出
2
有多种方案,如:除最后5只外,其余皆坐一辆车;最后5只坐第二辆车
数据范围与提示