Codeforces 629 C Famil Door and Brackets（dp）

Codeforces 629 C Famil Door and Brackets（dp）

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

• 在这任意n$n$个位置中都要满足前缀串的左括号数量大于等于右括号数量
  • 所有的左括号数量应和右括号数量相等

  • 求总的构造方案数。答案对 1e9+7 $1e9+7$取模。
    数据范围： 1≤m≤n≤100000,n−m≤2000 $1leq mleq nleq 100000,n-mleq 2000$
    分析：
    不妨将前缀左括号数量减去右括号数量的差值称为前缀和。那么题意就是任意位置前缀和非负。首先我们可以得到给出的长度为 m $m$的字符串的最小前缀和MIn$MIn$和最终的前缀和 tmp $tmp$，将 n $n$和m$m$的差值记为 diff $diff$,即 diff=n−m $diff=n-m$。
    考虑在这个长度为 m $m$的字符串前面安排长度为q$q$的括号字符串，除了这个长度为 q $q$的括号字符串自身需要满足在任意位置的前缀和都要大于等于0，还要满足最终的前缀和加上Min$Min$大于等于0。
    用 dp[i][j] $dp[i][j]$表示长度为 i $i$的串前缀和为j$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] $$当j=0时： qquad dp[i][j]=dp[i-1][j+1]\ 当j>0时： qquad 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 $$dp[0][0]=1,dp[1][0]=0,dp[1][1]=1,其余dp[i][j]=0$$
    因为要满足总串的前缀和为0，如果假设前面长度为 i $i$的串的前缀和为j$j$，中间长度为 m $m$的串的前缀和为tmp$tmp$，那么后面还剩下 n−i−m $n-i-m$个位置并且任意位置的前缀和应是大于等于 −(tmp+j) $-(tmp+j)$，但是将最后一个串反过来考虑，其实就是在长度为 n−i−m $n-i-m$的串中的任意前缀右括号的数量减去左括号的数量应大于等于 tmp+j $tmp+j$，这个的方案数和 dp[n−i−m][tmp+j] $dp[n-i-m][tmp+j]$应是一样的。最后前后方案数相乘，枚举前面串长度和前面串最终前缀和累加即可。
    时间复杂度： O((n−m)2) $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 = %dn", tmp, diff, Min);if((n & 1) || tmp > diff || -tmp > diff) {printf("0n");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 = %lldn", i, j, ans);}}printf("%I64dn", ans);}return 0;
    }