629C

629C

题目大意：给你一个由括号组成的字符串，长度为m，现在希望获得一个长度为n（全由括号组成）的字符串,0<=n-m<=2000这个长度为n的字符串要求有两个性质：就是任意前缀，左括号数量大于右括号数量字符串中左括号的数量等于右括号现在让你可以在长度为m的原串前加一个括号串p,在原串后加一个括号串q 最后p+m+q=n问有多少种组合p,q能得到目标串

题解：定义dp[i][j],为前缀长为i,且左括号数量-右括号数量=j的串有多少个，反过来也一样，最后dp*dp累加即可

不过要判断给定串中左括号很大的情况

1. #include <set>  
2. #include <map>  
3. #include <stack>  
4. #include <queue>  
5. #include <deque>  
6. #include <cmath>  
7. #include <vector>  
8. #include <string>  
9. #include <cstdio>  
10. #include <cstdlib>  
11. #include <cstring>  
12. #include <iostream>  
13. #include <algorithm>  
14. using namespace std;  
15. #define L(i) i<<1  
16. #define R(i) i<<1|1  
17. #define INF  0x3f3f3f3f  
18. #define pi acos(-1.0)  
19. #define eps 1e-9  
20. #define maxn 100100  
21. #define MOD 1000000007  
22.   
23. int n,m;  
24. char s[maxn];  
25. long long dp[2020][2020];  
26.   
27. int main()  
28. {  
29.     //freopen(&#","r",stdin);  
30.     //freopen(&#","w",stdout);  
31.     int t,C = 1;  
32.     //scanf("%d",&t);  
33.     while(scanf("%d%d",&n,&m) != EOF)  
34.     {  
35.         scanf("%s",s);  
36.         if(n & 1)  
37.         {  
38.             printf("0n");  
39.             continue;  
40.         }  
41.         int Max = -INF;  
42.         int l = 0,r = 0;  
43.         for(int i = 0; i < strlen(s); i++)  
44.         {  
45.             if(s[i] == '(')  
46.                 l++;  
47.             else  
48.                 r++;  
49.             Max = max(Max,r - l);  
50.         }  
51.         memset(dp,0,sizeof(dp));  
52.         dp[0][0] = 1;  
53.         for(int i = 1; i <= n-m; i++)  
54.             for(int j = 0; j <= i; j++)  
55.             {  
56.                 dp[i][j] = dp[i-1][j+1];  
57.                 if(j > 0)  
58.                     dp[i][j] += dp[i-1][j-1];  
59.                 dp[i][j] %= MOD;  
60.                 //printf("%d %d %dn",i,j,dp[i][j]);  
61.             }  
62.         long long ans = 0;  
63.         for(int i = 0; i <= n-m; i++)  
64.             for(int j = max(Max,0); j <= i; j++)  
65.             {  
66.                 if(l - r + j > n-m-i)  
67.                     break;  
68.                 ans += dp[i][j] * dp[n-m-i][j+l-r];  //正反等价交替
69.                 ans %= MOD;  
70.             }  
71.         printf("%lldn",ans);  
72.     }  
73.     return 0;  
74. }