lanqiaoOJ 1456 括号序列

#include<iostream>
#include<algorithm>
#include<cstring>
 
using namespace std ;
const LL N = 5010, M = 1e9 + 7 ;
typedef long long LL ;
LL n ;
LL f[N][N] ;
char s[N] ;
LL calc(){
  memset(f,0,sizeof f)
  f[0][0] = 1;
  for(int i = 1 ; i <= n ; i ++ ){
    if(s[i] == '(') {
      for(int j = 1 ; j <= n ; j ++){
        f[i][j] = f[i-1][j-1];//不用考虑dp[i][0] 因为dp[i-1][-1]是不合法的情况 不存在 为0
      }
    }
    else {
      f[i][0] = (f[i-1][0] + f[i-1][1]) %M;
      for(int j = 1 ; j <= n ; j ++){
        f[i][j] = (f[i-1][j+1] + f[i][j-1]) % M;
      }
    }
  }
  for(int i = 0 ;i <= n ; i ++){
    if(f[n][i]) return f[n][i];//我们需要的就是长度为len添加括号的合法情况，而从前往后遍历出现的第一个有可能的情况就是需要括号数最少的情况，因为左括号可以加很多个，我们仅需添加最少的情况
  }
}
 
 
int main(){
  scanf("%s" , s+ 1) ;
  n = strlen(s+1) ;
  LL  l = calc() ;
  reverse(s+1, s+1+n) ;
  for(int i = 1 ;i <= n ; i ++){
    if(s[i] == '(') s[i] = ')' ;
    else s[i] = '(' ;
  }
  LL r = calc() ;
  printf("%lld\n" , l*r % M) ;
  return 0 ;[]
  
}