Codeforces 629C Famil Door and Brackets(动态规划)

Dynamic programming

Posted by Scalpel on March 16, 2016

题目链接

题意:

给出一个只由构成的字符串s,其长度为m,在其前后分别添加字符串p和q,使其总长度为n,并且字符串的数量相等,任意前缀的的数量不少于,求有多少种p和q使字符串成立。

思路:

为字符串长度为i,的个数比多j个的方案数,初始化为,转移为可以互换,所以,然后枚举串s,求出数量的最小差值minum和最终的差值finum。因为括号要匹配,所以p和q是对称的,通过枚举p可得到q,枚举p的长度i,当并且时,可以把p放在s前面,q放在后面,此时q的方案数为,根据乘法原则,总的方案数增加

#include <iostream>

using namespace std;

#define FIO ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define FILEREAD freopen("input.txt", "r", stdin);

long long dp[2001][2001];
char s[100001];
const long long MOD = 1000000007;

int main()
{
    #ifndef ONLINE_JUDGE
        FILEREAD
    #endif
    FIO
    int n, m;
    cin >> n >> m;
    cin >> s;
    dp[0][0] = 1;
    for (int i = 1; i <= n - m; ++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]) % MOD;
    int finum = 0, minum = m;
    for (int i = 0; i < m; ++i)
    {
        if (s[i] == '(')
            ++finum;
        else
            --finum;
        if (minum > finum)
            minum = finum;
    }
    long long ans = 0;
    for (int i = 0; i <= n - m; ++i)
        for (int j = 0; j <= i; ++j)
            if (j > -minum && finum + j <= n - m -i)
                ans = (ans + dp[i][j] * dp[n - m - i][j + finum]) % MOD;
    cout << ans << '\n';
    return 0;
}