分数: 400 点
问题陈述
高桥和青木玩石头剪刀布 N 次。 [注:本游戏中,石头胜剪刀,剪刀胜布,布胜石头。]
青木的动作用字符串表示 S 长度 N 由字符组成 R, P,和 S。
的 i- 第一个字符 S 表示青木在 i第一场比赛: R 对于摇滚, P 对于纸张,以及 S 剪刀。
高桥的动作满足以下条件:
- 高桥从未输给青木。
- 对于 i=1,2,\ldots,N-1,高桥的举动 i- 第局棋与他在 (i+1)第一场比赛。
确定高桥可以赢得的最大比赛数。
保证高桥存在满足这些条件的一系列动作。
约束
- 1\leq N\leq2\times10 ^ 5
- S 是一个长度为的字符串 N 组成
R,P,和S. - N 是一个整数。
输入
输入由标准输入按以下格式给出:
N S
输出
打印高桥可能赢得的最大比赛数。
示例输入 1
6 PRSSRS
示例输出 1
5
在六场剪刀石头布中,青木玩的是布、石头、剪刀、剪刀、石头、剪刀。
高桥可以玩剪刀、布、石头、剪刀、布、石头来赢得第 1、2、3、5 和 6 场比赛。
高桥没有满足条件并赢得全部六场比赛的走法序列,因此打印 5.
示例输入 2
10 SSSSSSSSSS
示例输出 2
5
示例输入 3
24 SPRPSRRRRRPPRPRPSSRSPRSS
示例输出 3
18