Codeforces 629C Famil Door and Brackets

Codeforces 629C Famil Door and Brackets

合法的序列满足：

1. ( 和 ) 的个数相同。
2. 对于每个前缀，有左括号的个数>=右括号的个数

所以思路是，用 dp[i][j] 表示长度为长度为i，且左括号比右括号多j的串的个数。递推式可以写为：

dp[i][0] = dp[i-1][1]
dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#define fi first
#define se second
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
//head
LL dp[2005][2005]={0};
const int mod = 1e9+7;
const int INF = 0x3f3f3f3f;void init(int k)
{dp[0][0] = 1;for(int i=1; i<=k; i++){dp[i][0] = dp[i-1][1];for(int j=1; j<=k; j++)dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1]) % mod;}
}int main()
{int n,m;while(scanf("%d%d",&n,&m)!=EOF){string s;cin>>s;init(n-m);int pre = -INF;//在p中要多加入pre个前括号int suf;//在s中有suf个多余的前括号int sum1=0,sum2=0;for(int i=0; i<m; i++){if(s[i]==')'){sum1++;sum2--;}else{sum1--;sum2++;}pre = max(sum1, pre);}suf = sum2;LL ans = 0;for(int i=0; i<=n-m; i++)for(int j=max(0, pre); j<=n-m; j++){int k = j+suf;//在p中加的前括号抵消了s中的部分后括号if(k <= n-m){ans += (dp[i][j] * dp[n-m-i][k]) % mod;//dp[n-m-i][k] = dp[n-m-i][-k]，对称ans %= mod;}}printf("%I64dn", ans);}
}