Hoof, Paper, Scissors

题目描述

你可能听说过“石头、剪刀、布”这个游戏。奶牛们喜欢玩一个类似的游戏，叫做“蹄子、布、剪刀”。 “蹄子、布、剪刀”的规则很简单：两头奶牛互相对战。它们一起数到三，然后同时做出一种手势，表示蹄子、布或剪刀。 蹄子胜剪刀（因为蹄子能砸碎剪刀），剪刀胜布（因为剪刀能剪开布），布胜蹄子（因为蹄子可能被纸割伤）。例如，如果第一头奶牛出“蹄子”，第二头奶牛出“布”，那么第二头奶牛获胜。当然，如果两头奶牛出相同的手势，也可能打平。 农夫 John 想和他的获奖奶牛 Bessie 玩 $N$ 局“蹄子、布、剪刀”（$1 \leq N \leq 100,000$）。Bessie 作为这个游戏的高手，能够在 FJ 出手之前预测到他每一局的手势。不幸的是，Bessie 作为一头奶牛也很懒，因此她倾向于连续多次使用同一个手势。事实上，在整个 $N$ 局游戏中，她最多只愿意切换手势一次。例如，她可能在前 $x$ 局出“蹄子”，然后在剩下的 $N-x$ 局切换为出“布”。 给定 FJ 将要出的手势序列，请你确定 Bessie 最多能赢多少局。

输入格式

输入第一行是 $N$。 接下来的 $N$ 行为 FJ 的手势，每行一个字符，取值为 H、P 或 S。

输出格式

输出 Bessie 最多能赢的局数，前提是她在整个过程中最多只能改变手势一次。

5
P
P
H
P
S

4

提示

题目致谢：Mark Chen 和 Brian Dean

标签: USACO|2017|Silver

来源

USACO|2017|Silver