题意

　　对给定的对手的出拳顺序，如果只能按几个R，然后几个P，再几个S的顺序出拳（几个也可以是0个），那么求赢的方法有多少种。

分析

　　我原来想枚举P开始的位置和S开始的位置然后算得分，但是超时了o(╯□╰)o。。因为时间复杂度T（n^3）最大规模是500，而这里n≤1000。

　　用前缀和思想，s[i][0到2]储存前i个里有几个R、S、P，然后再枚举P、S开始位置为i、j；

　　0到i-1是R的时候，对方是S，我得分，可以得到s[i-1][1]分，对方是P，我失分，失去s[i-1][2]分，同理最后可以得到一个公式。

　　得分p=2*s[i-1][2]-s[i-1][1]+2*s[j-1][0]-s[i-1][0]-s[j-1][2]-s[n][0]+s[n][1]-s[j-1][1];得分大于0就是赢了。

　　这样时间复杂度是T（n^2）。

代码

AC代码

#include
     
      #include
      
       char c;int t,n,ans,p,s[1005][3];int main(){    scanf("%d",&t);    while(t--)    {        scanf("%d ",&n);        memset(s,0,sizeof(s));        for(int i=1; i<=n; i++){            c=getchar();            for(int j=0;j<3;j++)s[i][j]=s[i-1][j];            if(c=='R')s[i][0]++;            if(c=='P')s[i][1]++;            if(c=='S')s[i][2]++;        }        ans=0;        for(int i=1; i<=n+1; i++)            for(int j=i; j<=n+1; j++)            {                p=2*s[i-1][2]-s[i-1][1]+2*s[j-1][0]-s[i-1][0]-s[j-1][2]-s[n][0]+s[n][1]-s[j-1][1];                if(p>0)ans++;            }        printf("%d\n",ans);    }    return 0;}
      
     

超时代码

#include
     
      char s[1005];int t,n,ans,p;int main(){    scanf("%d",&t);    while(t--)    {        scanf("%d ",&n);        scanf("%s",s);        ans=0;        for(int i=0; i<=n; i++)            for(int j=i; j<=n; j++)            {                p=0;                for(int k=0; k
      
       =i&&k
       
        =j) p--;                        break;                    case 'P':                        if(k
        
         =j) p++;                        break;                    case 'S':                        if(k
         
          =i&&k
          
           0)ans++; } printf("%d\n",ans); } return 0;}