codeforces 629c C. Famil Door and Brackets

codeforces 629c C. Famil Door and Brackets

链接： 

题意： 给你一个长度为m的字符串，字符串中只有 (  he ) ，你要加入一些括号使得长度为n 并且满足合法，合法就是 左括号总数等于右括号总数，并且要求在任意一位置左括号数量>= 右括号数量 

思路： 参考： 

预处理出长度为 i  左括号比右括号多j 的方案数。

代码：

#include<bits/stdc++.h>using namespace std;
typedef long long ll;
const int N= 2005;
const ll mod=1e9+7;ll dp[N][N];
int n,m;
char s[100005];void init()
{dp[0][0]=1;for(int i=1;i<=2000;i++){dp[i][0]=dp[i-1][1];for(int j=1;j<=i;j++){dp[i][j]=(dp[i-1][j+1]+dp[i-1][j-1])%mod;}}
}int main()
{init();scanf("%d %d",&n,&m);scanf("%s",s+1);int sum=0;int mn=0x3f3f3f3f;for(int i=1;i<=m;i++){if(s[i]=='(') sum++;else sum--;mn=min(mn,sum);}int len=n-m;ll ans=0;for(int i=0;i<=len;i++){for(int j=0;j<=i;j++){if(j+mn<0) continue;  //  保证在任意一位置  左括号数量>= 右括号数量if(j+sum>len-i) continue;ll tmp=dp[i][j]*dp[len-i][j+sum]%mod; // j  表示左边的左括号比左边的右括号多多少// j+sum 表示右边的右括号比右边的左括号多多少ans=(ans+tmp)%mod;}}printf("%lldn",ans);return 0;
}