codeforces629C Famil Door and Brackets (dp)-白红宇

codeforces629C Famil Door and Brackets (dp)

阅读量：5343 次

发布时间：2019-06-15

本文共 2936 字，大约阅读时间需要 9 分钟。

As Famil Door’s birthday is coming, some of his friends (like Gabi) decided to buy a present for him. His friends are going to buy a string consisted of round brackets since Famil Door loves string of brackets of length n more than any other strings!

The sequence of round brackets is called valid if and only if:

the total number of opening brackets is equal to the total number of closing brackets;

for any prefix of the sequence, the number of opening brackets is greater or equal than the number of closing brackets.

Gabi bought a string s of length m (m ≤ n) and want to complete it to obtain a valid sequence of brackets of length n. He is going to pick some strings p and q consisting of round brackets and merge them in a string p + s + q, that is add the string p at the beginning of the string s and string q at the end of the string s.

Now he wonders, how many pairs of strings p and q exists, such that the string p + s + q is a valid sequence of round brackets. As this number may be pretty large, he wants to calculate it modulo 109 + 7.

Input

First line contains n and m (1 ≤ m ≤ n ≤ 100 000, n - m ≤ 2000) — the desired length of the string and the length of the string bought by Gabi, respectively.

The second line contains string s of length m consisting of characters '(' and ')' only.

Output

Print the number of pairs of string p and q such that p + s + q is a valid sequence of round brackets modulo 109 + 7.

      Examples 
        input 
4 1(
        output 
4
        input 
4 4(())
        output 
1
        input 
4 3(((
        output 
 0
 题意：给你一个长度为n的括号匹配串(不一定恰好匹配)，让你在这个串的前面和后面加上一些括号匹配串，使得这个括号串平衡(平衡的含义是对于任意位置的括号前缀和大于等于0，且最后的前缀和为0)。
 思路：比较容易想到的思路是枚举这个字符串前面p字符串的长度，那么后面q字符串的长度就知道了。那么p字符串要满足什么条件呢，因为要使得任意位置的前缀和大于等于0，所以我们可以使得p字符串的前缀和大于等于字符串s的最小前缀和minx，那么p+s就符合前缀和大于等于0，然后q的方案数也能确定了。我们用dp[i][j]表示i个括号平衡度为j的方案数，那么可以先预处理出来dp的值。然后我们算出s字符串的最小前缀和minx，最后我们只要枚举p的长度和平衡度c，那么sum+=dp[p][c]*dp[n-m-p][now+c],(now是整个s字符串的平衡度，考虑q的方案数时，我们要考虑对称性)。
 
 
#include
        #include
         #include
          #include
           #include
            #include
             #include
#include
               #include
                #include
                 #include
                  #include
                   using namespace std;typedef long long ll;typedef long double ldb;#define inf 99999999#define pi acos(-1.0)#define eps 1e-15#define maxn 100050#define MOD 1000000007char s[maxn];ll dp[2050][2060];int main(){ int n,m,i,j; while(scanf("%d%d",&n,&m)!=EOF) { scanf("%s",s+1); memset(dp,0,sizeof(dp)); dp[0][0]=1; for(i=1;i<=n-m;i++){ for(j=0;j<=i;j++){ if(j>0){ dp[i][j]=(dp[i][j]+dp[i-1][j-1])%MOD; } dp[i][j]=(dp[i][j]+dp[i-1][j+1])%MOD; if(dp[i][j]>=MOD)dp[i][j]-=MOD; } } int minx=inf; int now=0; for(i=1;i<=m;i++){ if(s[i]=='(')now++; else now--; minx=min(minx,now); } ll sum=0; for(i=0;i<=n-m;i++){ for(j=0;j<=i;j++){ if(j>=-minx && j+now<=n-m-i){ sum=(sum+dp[i][j]*dp[n-m-i][j+now ])%MOD; } } } printf("%I64d\n",sum); } return 0;}

转载于:https://www.cnblogs.com/herumw/p/9464547.html

你可能感兴趣的文章

MySQL添加、修改、撤销用户数据库操作权限的一些记录