Hoof, Paper, Scissors

题目描述

你可能听说过游戏“石头剪刀布”。奶牛们喜欢玩一个类似的游戏，称为“蹄子、布、剪刀”。

“蹄子、布、剪刀”的规则很简单。两头奶牛互相对战。她们都数到三，然后同时做出一个手势，表示蹄子、一张纸或一把剪刀。 蹄子胜剪刀（因为蹄子可以砸碎剪刀），剪刀胜纸（因为剪刀可以剪开纸），纸胜蹄子（因为蹄子会被纸割伤）。例如，如果第一头奶牛出“蹄子”，第二头奶牛出“纸”，则第二头奶牛获胜。当然，如果两头奶牛做出相同手势，也可能打平。

农夫约翰想和他的获奖奶牛贝茜进行 $N$ 局“蹄子、布、剪刀”比赛（$1 \leq N \leq 100,000$）。贝茜作为这项游戏的高手，能够在 FJ 出手之前预测出他的每一个手势。不幸的是，贝茜毕竟是头奶牛，也很懒。因此，她倾向于连续多次出同一种手势。事实上，在整组比赛中，她最多只愿意切换手势 $K$ 次（$0 \leq K \leq 20$）。例如，如果 $K=2$，她可能在前几局出“蹄子”，然后切换一段时间出“纸”，最后剩余比赛再出“蹄子”。

给定 FJ 将要出的手势序列，请求出贝茜最多能赢多少局。

输入格式

第一行包含 $N$ 和 $K$。 接下来的 $N$ 行包含 FJ 的手势，每行一个，取值为 H、P 或 S。

输出格式

在贝茜最多只能改变手势 $K$ 次的前提下，输出贝茜最多能赢的局数。

5 1
P
P
H
P
S

4

提示

题目致谢：Mark Chen 和 Brian Dean

标签: USACO|2017|Gold

来源

USACO|2017|Gold