codeforces C. Famil Door and Brackets dp

codeforces C. Famil Door and Brackets dp

题意

有个字符串由(,)组成。并且从左往右数时保证(的数量不小于)，并且括号是匹配的。现在给该串中间的一部分，求符合要求的串的个数。

思路

简单的想法就是枚举给出串的左边的(,)的个数，然后计算出另一个串的个数。然后相乘，累加。

于是要保证这样填充的时候满足串的要求。这个可以根据符号个数进行判断。

dp[i][j] 表示i个(j个)满足题目要求的情况下的方案数。

dp[i][j] = dp[i-1][j] + dp[i][j-1];

而右边的串的方案数其实可以用左边的dp来处理，就是(,)相反的情况。

特判一些无法得出答案的情况比如n为奇数的时候。

code

#include <bits/stdc++.h>
using namespace std;const long long MOD = 1e9 + 7;#define debug(a) cout << #a << ": "<< a << endlint n, m, _n;
long long ans;
char s[100000 + 5];long long dp[2000 + 5][2000 + 5];int main () {scanf ("%d %d", &n, &m);scanf ("%s", &s);int _n = n / 2;memset(dp, 0, sizeof dp);dp[0][0] = 1LL;for (int i=1; i<=2000; i++) {for (int j=0; j<=i; j++) {dp[i][j] = 1LL * (dp[i-1][j] + dp[i][j-1]) % MOD;}}int cnt_left = 0, cnt_right = 0, cnt_ma = 0, cnt_mi = 0, cnt_ss = 0;int len = strlen(s);for (int i=0; i<len; i++) {if (s[i] == '(') {cnt_left ++;cnt_ss ++;} else {cnt_ss --;} if (cnt_ss < 0) cnt_mi = min(cnt_ss, cnt_mi);}cnt_ss = 0;for (int i=len-1; i>=0; i--) {if (s[i] == ')') {cnt_ss ++;cnt_right ++;} else {cnt_ss --;}if (cnt_ss < 0) cnt_ma = min(cnt_ss, cnt_ma);}ans = 0LL;if(n % 2 == 1 ||  cnt_left > _n || cnt_right > _n || (n-m) < abs(cnt_left - cnt_right)) {printf ("%I64dn", ans);return 0;}for (int i=0; i<= _n-cnt_left; i++) { for (int j=0; j<=i; j++) {if (i - j >= -cnt_mi) {int _l = _n - cnt_right - j;int _r = _n - cnt_left - i;if (_l < 0 || _r < 0 || _l < _r) continue;if (-cnt_ma <= _l - _r) {                    ans = (ans +(dp[i][j] * dp[_l][_r])%MOD ) % MOD;}}}}printf ("%I64dn", ans);return 0;   
}