题目传送门
本博客由南昌理工赞助支持。
译文描述
您可能听说过“岩石，纸，剪刀”游戏。奶牛喜欢玩类似的游戏，他们称之为“蹄，纸，剪刀”。

“蹄，纸，剪刀”的规则很简单。两只母牛互相对抗。他们都数到三，然后每个人同时做出一个代表蹄，一张纸或一把剪刀的手势。蹄打剪刀（因为蹄可以砸掉一把剪刀），剪刀打纸（因为剪刀可以剪纸），而纸拍着蹄（因为蹄可以剪纸）。例如，如果第一头母牛做出“蹄”手势，而第二头做出“纸”手势，则第二头母牛获胜。当然，如果两头牛都做出相同的手势，也可以打领带。

农夫约翰想在N场“蹄，纸，剪刀”游戏中与他的牛Bessie对抗（1 ≤ñ≤1 0 0 ，0 0 0）。作为游戏专家的Bessie可以在FJ做出动作之前预测每个动作。不幸的是，作为牛的贝茜也很懒。结果，她倾向于连续多次打相同的手势。实际上，她只愿意在整个游戏中最多切换一次手势 。例如，她可能在开始的x 场比赛中扮演“蹄子” ，然后对于其余的n - x 场比赛切换到“纸” 。

输入描述：
输入文件的第一行包含N。
其余N行包含FJ的手势，每个手势为H，P或S。
输出描述：
打印Bessie最多可以赢的游戏数，因为她最多只能更改一次手势。
示例1
输入
5
P
P
H
P
S
输出
4
题意精简如下
两头牛猜剪刀（S)石头(P)布(H)， a牛作弊，他知道b牛的N次出手动作，但a牛很懒，她往往会连续多次打出同样的动作。但a牛最多只愿意在整套游戏中切换一次动作，问a牛最多能赢多少次。
解题思路
先想暴力做法，再逐步优化。
暴力思路如下：
设最多可以赢的游戏数为ans = 0;
要改变一次手势的话，可以改变为其他两种，或者不变（比如对方全出石头， 我方肯定全出布,才能赢的最多）。
先假设a牛刚开始出剪刀，在第i场前和在第i场换成石头 / 布 / 剪刀后，看总共能赢多少次，算出答案 a1 / a2 / a3， 和 ans 取最大值。
再假设a牛刚开始出石头，在第i场前和在第i场换成石头 / 布 / 剪刀后，看总共能赢多少次，算出答案 a1 / a2 / a3， 和 ans 取最大值。
最后假设a牛刚开始出布，在第i场前和在第i场换成石头 / 布 / 剪刀后，看总共能赢多少次，算出答案 a1 / a2 / a3， 和 ans 取最大值。
然后输出最多可以赢的游戏数 ans.
暴力做法：
每次暴力要枚举改换手势的场数i，然后统计前i场石头 / 布 / 剪刀各自赢的次数，加上后n - i场改换后赢的场数，取最大值。
暴力做法没有考虑时间复杂度，如果数据较小，可以直接交暴力解法，但本题数据1e5暴力必超时，要想办法优化。
优化思路：
想办法用学过的算法对暴力做法中的步骤进行优化，在经过一番思索后，我发现前缀和正好能对暴力做法中的统计赢的场数进行优化。
优化做法：
可以用前缀和来统计一直出一种方案的赢的次数，当在第i场游戏要转换成别的手势时，前缀和正好能很快的算出改变手势后的（ n - i )场赢的次数。
1.统计石头，剪刀，布的前缀和
2.当到第i个时，统计前i个x(x为石头或剪刀或布)与后n - i 个y(y为石头或剪刀或布)的最大值.
代码实现

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 3;
int a[N];
int sum[4][N];
int n;
int x, y, z;
int ans;
int main()
{
    cin >> n;//输入n场对方出手势
    char e;
    for (int i = 1; i <= n; ++i) {
        cin >> e;//转化一下
        if (e == 'H') a[i] = 0;//出 0 能赢
        else if (e == 'P') a[i] = 1;//出 1 能赢
        else if (e == 'S') a[i] = 2;// 出2 能赢
    }
    for (int i = 1; i <= n; ++i) {
        int u = a[i];
        for (int j = 0; j < 3; ++j) {
            if (u == j) sum[j][i] = sum[j][i - 1] + 1;//如果能赢，即在上场的基础上加1
            else sum[j][i] = sum[j][i - 1];//否则不变
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                int u = sum[j][i] + (sum[k][n] - sum[k][i]);//，统计前i个x(x为石头或剪刀或布)与后n - i 个y(y为石头或剪刀或布)能赢的场数
                ans = max(u, ans);//和答案取最大值
            }
        }
    }
    cout << ans << endl;//输出最多能赢场数
    return 0;
}