C. Famil Door and Brackets DP

C. Famil Door and Brackets DP

C. Famil Door and Brackets
题意：给定长度为m的字符串，需要你构造长度为n的字符串，且该字符串括号匹配，你可以在长度为m的字符串前面和后面添加字符串，问你有多少种构造方法。
题解：dp[i][j]代表有i个’（’ ，j个‘）’能构造字符串的切括号匹配的字符串数量。
一定保证i>=j。
dp[i][j] = dp[i-1][j] + dp[i][j-1];
那么我们计算答案贡献的时候，注意要保证前缀串 （i - j）的数量要大于等于给定字符串i-j的最小前缀，同样保证后缀串。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5+10,mod = 1e9+7;
char s[maxn];
ll dp[2020][2020];
int main()
{int n,m; scanf("%d%d ",&n,&m);scanf("%s",s+1);int len = strlen(s+1);memset(dp,0,sizeof(dp));dp[0][0] = 1LL;for(int i=1;i<2010;i++){for(int j=0;j<=i;j++)if(j>0)dp[i][j] = (dp[i][j-1]+dp[i-1][j]) % mod;else dp[i][j] = dp[i-1][j];}int left = 0, right = 0, mn_l = 0, mn_r = 0, sum = 0;int _n = n/2;for (int i=1; i<=len; i++) {if (s[i] == '(') {left ++;sum ++;} else {sum --;right ++;}mn_l = min(sum, mn_l);}sum = 0;for (int i=len; i>0; i--) {if (s[i] == ')') {sum ++;} else {sum --;}mn_r = min(sum, mn_r);}ll   ans = 0LL;if(n % 2 == 1 ||  left > _n || right > _n || (n-m) < abs(left - right)) {printf ("%lldn", ans);return 0;}for (int i=0; i<= _n-left; i++) {for (int j=0; j<=i; j++) {if (i - j >= -mn_l) {int _l = _n - right - j;int _r = _n - left - i;if (_l < 0 || _r < 0 || _l < _r) continue;if (-mn_r <= _l - _r) {ans = (ans +(dp[i][j] * dp[_l][_r])%mod ) % mod;}}}}printf ("%lldn", ans);}