对给定的对手的出拳顺序,如果只能按几个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)。
#include<stdio.h>
#include<cstring>
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<stdio.h>
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<n; k++)
switch(s[k])
{
case 'R':
if(k>=i&&k<j) p++;
else if(k>=j) p--;
break;
case 'P':
if(k<i) p--;
else if(k>=j) p++;
break;
case 'S':
if(k<i) p++;
else if(k>=i&&k<j) p--;
break;
}
if(p>0)ans++;
}
printf("%d\n",ans);
}
return 0;
}