再做水题就没救了
考虑DP。。。我们把正反面一起弄
fi,j,k,u表示第几个位置，正面多了多少左括号，背面多了多少没办法消的右括号，背面结尾的左括号数
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> using namespace std; typedef long long LL; LL f[51][51][51][51]; char ss[110]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%s",ss+1); int n=strlen(ss+1); memset(f,0,sizeof(f)); if(ss[1]=='S')f[1][1][0][1]=1; else f[1][1][1][0]=1; for(int i=1;i<n;i++) for(int j=0;j<=i;j++) for(int k=0;k<=i;k++) for(int u=0;u+k<=i;u++) if(f[i][j][k][u]>0) { if(ss[i+1]=='S') { f[i+1][j+1][k][u+1]+=f[i][j][k][u]; if(j>0) { if(u>0)f[i+1][j-1][k][u-1]+=f[i][j][k][u]; else f[i+1][j-1][k+1][u]+=f[i][j][k][u]; } } else { if(u>0)f[i+1][j+1][k][u-1]+=f[i][j][k][u]; else f[i+1][j+1][k+1][u]+=f[i][j][k][u]; if(j>0)f[i+1][j-1][k][u+1]+=f[i][j][k][u]; } } LL ans=0; for(int j=0;j<=n;j++) ans+=f[n][j][j][0]; printf("%lld ",ans); } return 0; }