codeforces 629C Famil Door and Brackets (dp + 枚举)

题目链接：

　　codeforces 629C Famil Door and Brackets

题目描述：

　　给出完整的括号序列长度n，现在给出一个序列s长度为m。枚举串p，q，使得p+s+q是合法的括号串，长度为n，问p，q的取值数目。

解题思路：

　　枚举p的长度，可以直接得到q的长度。因为要满足在任意位置'(' 数目大于 ’)‘ 的数目，所以统计一下s串中 ’(‘ - ')' 的最小数目minx。dp[i][j] 代表到位置 i 时，满足 '(' - ')' == j 的情况数目。然后枚举p的 j (i > -minx)，然后根据p串推出q串满足合法串的状态，两者相乘。

 #include <bits/stdc++.h>

 using namespace std;

 typedef __int64 LL;

 const int INF = 1e9 + ;

 const int maxn = ;

 const int N = ;

 const int mod = 1e9+;

 ///dp[i][j] 到第i个位置，有j个不平衡(括号

 LL dp[N][N], n, m;

 char str[maxn];

 void init ()

 {

     int num = ;

     memset (dp, , sizeof(dp));

     dp[][] = ;

     for (int i=; i<=num; i++)

         for (int j=; j<=i; j++)

         {

             if (j > )

                 dp[i][j] = (dp[i][j] + dp[i-][j-]) % mod;

             dp[i][j] = (dp[i][j] + dp[i-][j+]) % mod;

         }

 }

 LL solve ()

 {

     int minx = INF, tmp = , num = n - m;

     for (int i=; str[i]; i++)

     {

         if (str[i] == '(')

             tmp ++;

         else

             tmp --;

         minx = min (minx, tmp);

     }

     LL ans = ;

     for (int i=; i<=num; i++)

         for (int j=; j<=i; j++)

             if (j >= -minx && num-i >= j + tmp)

                 ans = (ans + dp[i][j]*dp[num-i][j+tmp]) % mod;

     return ans;

 }

 int main ()

 {

     init ();

     while (scanf ("%I64d %I64d", &n, &m) != EOF)

     {

         scanf ("%s", str);

         printf ("%I64d\n", solve ());

     }

     return ;

 }

巴特西

codeforces 629C Famil Door and Brackets (dp + 枚举)

最新文章

热门文章