Codeforces 629 C Famil Door and Brackets（dp）_综合

题目链接；
Codeforces 629 C Famil Door and Brackets
题意：
给一个长度为 $m$ 的且只含 $"(",")"$ 的字符串，可以在这个字符串左右添加长度分别为 $p,q$ 的只含 $"(",")"$ 的字符串使得总长度为 $n$ ，但是要满足：

在这任意 n 个位置中都要满足前缀串的左括号数量大于等于右括号数量
- 所有的左括号数量应和右括号数量相等
- 求总的构造方案数。答案对 $1e9+7$ 取模。
  数据范围： $1\leq m\leq n\leq 100000,n-m\leq 2000$
  分析：
  不妨将前缀左括号数量减去右括号数量的差值称为前缀和。那么题意就是任意位置前缀和非负。首先我们可以得到给出的长度为 $m$ 的字符串的最小前缀和 $MIn$ 和最终的前缀和 $tmp$ ，将 $n$ 和 $m$ 的差值记为 $diff$ ,即 $diff=n-m$ 。
  考虑在这个长度为 $m$ 的字符串前面安排长度为 $q$ 的括号字符串，除了这个长度为 $q$ 的括号字符串自身需要满足在任意位置的前缀和都要大于等于0，还要满足最终的前缀和加上 $Min$ 大于等于0。
  用 $dp[i][j]$ 表示长度为 $i$ 的串前缀和为 $j$ 的方案数，状态转移方程：
  
  当j=0时：dp[i][j]=dp[i?1][j+1]当j>0时：dp[i][j]=dp[i?1][j?1]+dp[i?1][j+1]
  
  初始化:
  
  dp[0][0]=1,dp[1][0]=0,dp[1][1]=1,其余dp[i][j]=0
  
  因为要满足总串的前缀和为0，如果假设前面长度为 i 的串的前缀和为 j ，中间长度为 m 的串的前缀和为 tmp ，那么后面还剩下 n?i?m 个位置并且任意位置的前缀和应是大于等于 ?(tmp+j) ，但是将最后一个串反过来考虑，其实就是在长度为 n?i?m 的串中的任意前缀右括号的数量减去左括号的数量应大于等于 tmp+j ，这个的方案数和 dp[n?i?m][tmp+j] 应是一样的。最后前后方案数相乘，枚举前面串长度和前面串最终前缀和累加即可。
  时间复杂度： O((n?m)2) 。
```
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <climits>
#include <cmath>
#include <ctime>
#include <cassert>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
typedef long long ll;
const int MAX_N = 100010;
const int MAX_M = 2010;
const ll mod = (ll)(1e9) + 7;int n, m;
char s[MAX_N];
ll dp[MAX_M][MAX_M];int main()
{while(~scanf("%d%d", &n, &m)) {scanf("%s", s);int Min = MAX_N, tmp = 0;for (int i = 0; i < m; ++i) {if (s[i] == '(') tmp++;else tmp--;Min = min(Min, tmp); }int diff = n - m;//printf("tmp = %d diff = %d Min = %d\n", tmp, diff, Min);if((n & 1) || tmp > diff || -tmp > diff) {printf("0\n");continue;}memset(dp, 0, sizeof(dp));dp[0][0] = 1;dp[1][0] = 0, dp[1][1] = 1;for (int i = 2; i <= diff; ++i) {for (int j = 0; j <= i; ++j) {if(j == 0) dp[i][j] = dp[i - 1][j + 1];else dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];dp[i][j] %= mod;}}ll ans = 0;int st = 0;if(Min < 0) st = -Min;for (int i = st; i <= diff; ++i) {for (int j = st; j <= i; ++j) {ans = (ans + dp[i][j] * dp[n - i - m][j + tmp] % mod) % mod;//printf("i = %d j = %d ans = %lld\n", i, j, ans);}}printf("%I64d\n", ans);}return 0;
}
```