54 lines
1.8 KiB
C++
54 lines
1.8 KiB
C++
// lanqiao 1456 括号序列
|
||
#include<bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
const int N = 5e3 + 10, mod = 1e9 + 7;
|
||
int n;
|
||
string str;
|
||
// 状态: dp[i][j]表示前i个字符中有j个左括号待匹配时的方案的数量
|
||
int dp[N][N];
|
||
int calc(){
|
||
memset(dp, 0, sizeof dp);
|
||
dp[0][0] = 1; // 表示没有任何括号的情况下只有一种可能
|
||
for(int i = 1; i <= n; i++){
|
||
if(str[i] == '('){
|
||
// 遍历所有可能的未匹配的左括号的数量
|
||
for(int j = 1; j <= n; j++){
|
||
// 因为遇到了左括号，需要匹配的左括号的数量减1
|
||
dp[i][j] = dp[i-1][j-1];
|
||
}
|
||
}else{ // 右括号
|
||
// 如果之前没有未匹配的左括，只能添加一个左括号，否则可以不添加或添加一个左括号
|
||
dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % mod;
|
||
// 遍历所有可能的未匹配的左括号的数量
|
||
for(int j = 1; j <= n; j++){
|
||
// 因为遇到了右括号，需要匹配的左括号的数量增加1，或者添加一个右括号来消除一个未匹配的左括号
|
||
dp[i][j] = (dp[i-1][j+1] + dp[i][j-1]) % mod;
|
||
}
|
||
|
||
}
|
||
}
|
||
for(int i = 0; i <= n; i++){
|
||
if(dp[n][i]){ // 如果存在合法方案
|
||
return dp[n][i];
|
||
}
|
||
}
|
||
return -1;
|
||
}
|
||
signed main(){
|
||
cin >> str;
|
||
n = str.size();
|
||
str = ' ' + str;
|
||
int l = calc(); // 计算添加左括号使之合法的方案
|
||
reverse(str.begin() + 1, str.end()); // 反转括号序列
|
||
for(int i = 1; i <= n; i++){
|
||
if(str[i] == '(') str[i] = ')';
|
||
else str[i] = '(';
|
||
}
|
||
int r = calc();
|
||
cout << (l*r) % mod << endl;
|
||
return 0;
|
||
}
|
||
/* test samples -> 5
|
||
((()
|
||
*/ |