P6120 [USACO17JAN] Hoof, Paper, Scissor S

难度：普及/提高−；

题意：

​ 石头、剪刀、布游戏，先给出 $n$ 轮已经知道的其中一人的对局情况，例如样例：

5
P - 布
P - 布
H - 石头
P - 布
S - 剪刀

另外一人，只允许修改一次机会的情况下，求最多可以赢的局面数量。

分析：

​ 题意理解了，我感觉就是很简单，可以用双指针做，也可以用前缀和分开两段来做。这里讲述前缀和分两段的分别统计贡献的方式来做。

​ 根据题意可知，手势一旦确定为 $x$，那么只允许在后面第 $k$ 次发生了修改为 $y$，那么贡献(胜利的局数)就是 $k[x{]}_{1\sim x}+k[y{]}_{x\sim n}$，其中 $k$ 数组可以用前缀和来完成。

参考代码：

#include <bits/stdc++.h>
#define ll long longconst int N = 100050;
int h[N], s[N], p[N], n;int mx(int a, int b) // 为了让代码看起来简短一些
{if (a > b)return a;return b;
}int main()
{std::ios::sync_with_stdio(false), std::cin.tie(nullptr);std::cin >> n;for (int i = 1; i <= n; i++){h[i] = h[i - 1], s[i] = s[i - 1], p[i] = p[i - 1];char ch;std::cin >> ch;if (ch == 'H')h[i]++;if (ch == 'S')s[i]++;if (ch == 'P')p[i]++;}int ans = 0;for (int i = 1; i <= n; i++) // [1-i], [i+1,n] 找出区间内最长的两段ans = mx(ans, mx(h[i], mx(s[i], p[i])) + mx(h[n] - h[i], mx(s[n] - s[i], p[n] - p[i])));std::cout << ans << '\n';return 0;
}