bzoj#P4760. [USACO2017 Jan] Hoof, Paper, Scissors
[USACO2017 Jan] Hoof, Paper, Scissors
题目描述
你可能玩过石头剪刀布这个游戏,奶牛们也喜欢玩类似的游戏,叫做“蹄子剪刀布”。
蹄子剪刀布的规则和石头剪刀布的规则是一样的,蹄子踩碎剪刀,剪刀剪布,布包蹄子。
现在 FJ 想要和他的最机智的奶牛 Bessie 玩蹄子剪刀布(我也不知道 FJ 为什么有蹄子),一共进行了 轮,Bessie,作为一个奶牛,非常的怠惰,无论她出什么,都喜欢连续的出,最多变化 次,也就是说,对于她所出的,记为序列 ,记 为有多少个 满足 (),而她的 一定不会超过 。
现在 FJ 已经给出了他出的东西,你要告诉 Bessie,在不确定她出的东西的情况下,她最多能赢多少次。
输入格式
输入数据第一行为 。
接下来 行表示 FJ 所出的东西,H
表示 hoof,P
表示 paper,S
表示 Scissors。
输出格式
输出在变化不超过 次的前提下,最多能赢多少次。
5 1
P
P
H
P
S
4
数据规模与约定
对于 的数据,,。
题目来源
Gold