分数: 300 点
问题陈述
AtCoDeer 鹿和他的朋友 TopCoDeer 正在玩游戏。 游戏由 N 转。 在每一回合中,每个玩家都扮演两个角色中的一个 手势, 摇滚 和 纸,如石头剪刀布,在以下条件下:
(※) 每回合后,(玩家玩纸的次数)≦(玩家玩摇滚的次数)。
每个玩家的得分计算方式为(玩家获胜的回合数) - (玩家失败的回合数),每回合的结果由剪刀石头布的规则决定。
(对于那些不熟悉剪刀石头布的人来说:如果一个玩家玩石头,另一个玩家玩布,则后一个玩家获胜,前一个玩家输。如果两个玩家都做出相同的手势,则该回合为平局,没有玩家获胜或失败。)
AtCoDeer凭借他的超能力,能够预见到TopCoDeer在每场比赛中会做出的手势。 N 回合,游戏开始前。 规划 AtCoDeer 在每个回合中的手势,以最大化 AtCoDeer 的得分。
TopCoDeer 每回合将播放的手势由字符串给出 s。如果 i-th (1≦i≦N) 中的字符 s is g, TopCoDeer 将在 i第回合。同样,如果 i-th (1≦i≦N) 的性格 s in p, TopCoDeer 将在 i第回合。
约束
- 1≦N≦10^5
- N=|s|
- 中的每个字符 s is
gorp. - 代表的手势 s 满足条件(※)。
输入
输入由标准输入按以下格式给出:
s
输出
打印 AtCoDeer 的最大可能分数。
示例输入 1
gpg
示例输出 1
0
每回合与对手做出相同的手势,得分为 0,这是可能的最大分数。
示例输入 2
ggppgggpgg
示例输出 2
2
例如,考虑按以下顺序播放手势:石头、纸、石头、纸、石头、石头、纸、纸、石头、纸。此策略取得三胜一负,得分为 2,这是可能的最大分数。