题目描述(ID:12372)
标题: 塔防游戏
标签:
详情:
源码巨人的攻击开始了。
他的大军由三种主要战斗单位组成:帕拉丁机器人(PaladinP),九头蛇战舰(HydraliskH)和自爆者飞机(SacrificerS)。他会用这些大军对编程星球发动一共N波次进攻,每次进攻只会使用一种战斗单位。
幸运的是,啊哈沃德的旗舰装备了威力巨大的大和炮,一击就可以消灭一整波进攻的敌人。但不幸的是,大和炮攻击需要锁定目标。如果啊哈沃德将目标锁定为P,那么他可以拦截后面波次中的所有的P,但会漏过所有的HS
啊哈沃德提前侦查了源码巨人的攻击顺序,他一共有M次调整大和炮锁定目标的机会,例如,当M=2时,他可以首先将目标锁定为P,之后调整为H,之后再调整为S,以拦截下更多的目标。
在已知源码巨人N次进攻顺序和大和炮调整次数M的基础上,请计算啊哈沃德一共能够拦截多少次源码巨人的进攻。
输入格式:
第一行有两个整数,N(1<=N<=100000),M(0<=M<=20)。
接下来N行每行包含一个P,H或者S字符,代表源码巨人的进攻单位。
输出格式:
输出一个整数,代表在大和炮改变目标不超过M次时,最多能够拦截下的进攻波次。
限制: 对于20%数据,N<=100,M<=1
对于40%数据,N<=1000,
对于70%数据,N<=20000,
对于100%数据,N<=100000,M<=20
样例:

输入

9 1
S
H
S
S
H
H
P
H
S

输出

6

解释

在有1次调整攻击目标的情况下,应该首先把目标设置为S,拦截下前4波攻击中的第1,3,4波;然后将目标调整为H,拦截下剩下攻击中的第5,6,8波。因此最多可以拦截下6波进攻。
登录并解答