【Codeforces629C】Famil Door and Brackets [DP]

【Codeforces629C】Famil Door and Brackets [DP]

Description

Input

Output

Sample Input

Sample Output

HINT

Solution

　　显然，我们考虑运用DP。先求出 f[i][j] 表示 长度为 i 的括号序列，“)” 比 “(” 多 j 个的方案（时刻保证 j >= 0）。

　　然后我们考虑怎样获得答案。先预处理出L，R表示将读入的括号序列消去若干对之后剩下的“)” “(”个数（消去吼显然形如“))(((”）。

　　那么我们左边要加入的就要至少多R个“(”，右边类似。

　　但是显然，我也可以左边再多填几个“(”，右边再多填几个“)”。

　　那么我们就可以 枚举左边填 i 个括号（则右边填 need - i 个），左边多填 num 个“(”（则右边多填 num 个“)”）。

　　然后统计答案即可。

Code

 1 #include<iostream>  
 2 #include<string>  
 3 #include<algorithm>  
 4 #include<cstdio>  
 5 #include<cstring>  
 6 #include<cstdlib>  
 7 #include<cmath>
 8 using namespace std;
 9 typedef long long s64;
10  
11 const int ONE = 800005;
12 const int MOD = 1e9 + 7;
13 const int Base = 2005;
14 
15 int n, m, need;
16 char s[ONE];
17 int f[2005][2005];
18 int Ans;
19 int stk[ONE], top;
20 int L = 0, R = 0;
21 
22 int get() 
23 { 
24         int res;char c; 
25         while( (c=getchar())<48 || c>57 );
26         res=c-48;  
27         while( (c=getchar())>=48 && c<=57 ) 
28         res=res*10+c-48; 
29         return res; 
30 } 
31 
32 void Deal_f()
33 {
34         f[0][0] = 1;
35         for(int i = 1; i <= need; i++)
36             for(int j = 0; j <= need; j++)
37             {
38                 f[i][j] = (f[i][j] + f[i - 1][j + 1]) % MOD;
39                 if(j >= 1) f[i][j] = (f[i][j] + f[i - 1][j - 1]) % MOD;
40             }
41 }
42 
43 void Deal_LR()
44 {
45         for(int i = 1; i <= m; i++)
46         {
47             if(s[i] == ')' && stk[top] == '(') top--;
48             else stk[++top] = s[i]; 
49         }
50 
51         for(int i = 1; i <= top; i++)
52             if(stk[i] == '(') L++;
53             else R++;
54 }
55 
56 int main()
57 {
58         n = get();    m = get();    need = n - m;
59         scanf("%s", s + 1);
60 
61         Deal_f(), Deal_LR();
62 
63         Ans = 0;
64         for(int i = 0; i <= need; i++)
65             for(int num = 0; num <= need; num++)//left's L
66                 if(R + num < 2005 && L + num < 2005)
67                        Ans = (Ans + (s64)f[i][R + num] * f[need - i][L + num] % MOD) % MOD;
68 
69         printf("%d", Ans);
70 }

• 视图代码

转载于:.html