USACO 2017 JAN hoof... Silver 题解

这题我发现大部分神犇都是用DP做的，然而需要吗？

首先我们可以考虑暴力，我们可以外层枚举哪一局换手势，内层算能赢多少局，这样复杂度是的。

之后我没就可以考虑优化，我们发现外层循环是优化不掉的，至少很难优化掉，我们可以优化内层使得查询每一次是的，怎么办呢？很显然我们只要用一个前缀和维护。计算赢多少局时我们只需要看输给他的那个手势出了多少次就行了。

细节声明：

1，要开三个前缀和数组来维护赢多少局（一共三种手势

2，当我们计算换了之后的手势等赢多少局时，应该是。是当前下标。

3，别忘了还要分别枚举换之前手势是什么，和换之后是什么。由于可能不换，所以只要写一下如下循环就可以了

for(int i=1;i<=3;i++)
{
    for(int j=1;j<=3;j++)//我们不需要判断i是否等于j,因为可以一直不换
    {
    }
}

这样我们的代码就出来啦！

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n+5];
    int h[n+5],s[n+5],p[n+5];//三个前缀和数组
   //A数组其实没啥用
    s[0]=h[0]=p[0]=0;
    for(int i=1;i<=n;i++)
    {
        char c;
        cin>>c;
        s[i]=s[i-1];
        h[i]=h[i-1];
        p[i]=p[i-1];
        if(c=='H')
        {
            a[i]=1;
            h[i]++;//记录蹄子出了多少次
        }
        if(c=='S')
        {
            a[i]=2;
            s[i]++;//记录剪刀出了多少次
        }
        if(c=='P')
        {
            a[i]=3;
            p[i]++;//记录纸出了多少次
        }
    }if(max(p[n],max(h[n],s[n]))==n)//如果全是一个手势就输出N
    {
        cout<<n;
        return 0;
    }
    int ans=0;
    for(int i=1;i<=3;i++)
    {
        for(int j=1;j<=3;j++)
        {
            for(int k=1;k<=n;k++)
            {
                int sum=0;
                if(i==1)
                sum+=s[k];
                if(i==2)
                sum+=p[k];
                if(i==3)
                sum+=h[k];
                if(j==1)
                sum+=s[n]-s[k-1];
                if(j==2)
                sum+=p[n]-p[k-1];
                if(j==3)
                sum+=h[n]-h[k-1];
                       //算赢了多少局
                ans=max(ans,sum);//记录最大值
            }
        }
    }
    cout<<ans;//输出
    return 0;
}