题解 P6120 【[USACO17JAN]Hoof, Paper, Scissor S】

· · 题解

楼下的人的代码都很长抄都不想抄，但真的这么复杂吗？

首先，如果要在第 k 次变，前面是出x手势，后面出y手势，那么就是k[x]_{1-x}+k[y]_{x-n}。

其实k数组是可以用前缀和完成。

所以代码显而易见，由于我说不是很清楚，具体细节看代码。

喜闻乐见的代码：

#include<bits/stdc++.h>
using namespace std;
int n,s[100001],p[100001],h[100001],ans;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        s[i]=s[i-1];//s的前缀和
        p[i]=p[i-1];//p的前缀和
        h[i]=h[i-1];//h的前缀和
        char c;
        cin>>c;
        if(c=='S')
            s[i]++;
        if(c=='P')
            p[i]++;
        if(c=='H')
            h[i]++;
    }
    for(int i=1;i<=n;i++)
        ans=max(ans,max(s[i],max(p[i],h[i]))/*前面最多的*/+max(s[n]-s[i],max(p[n]-p[i],h[n]-h[i])/*后面最多的（因为最多换一次所以可以不换）*/));
    cout<<ans;
    return 0;
}