题目

链接

题意

略

题解

括号序列的性质：

(1) 左、右括号的数量相等

(2) 任意前缀的左括号数量必须大于等于右括号数量

最少需要添加括号的数量：

(1) 为了尽可能添加少的括号，所以添加的左、右括号不会出现如同“()”的形式。

(2) 从前往后遍历，当前前缀中，若左括号的数量小于右括号的数量，则需要添加对应数量的左括号，若遍历结束后左括号数量大于右括号，则需要添加对应数量的右括号。

通过上面的分析，我们发现，我们的分析对题目好像没有什么卵用

添加括号的方案：

(1)左括号与右括号添加的位置方案是相互独立的，不会相互影响，即使左、右括号添加在同一个间隙，因为不能存在"()"的形式，此处只能为类似"))(("的一种形式，故总的方案数等于左括号的方案数 × 右括号的方案数。

(2)单独考虑添加左括号，若以右括号为分割点， 将整个序列进行分割，因为分割后的子串中均为左括号， 添加任意数目的左括号方案数均为一种，那么此时，我们仅需考虑添加不同数量的左括号的方案数即可。

(3)右括号同理

动态规划：

f[i][j]的状态表示

(1)集合：只考虑前 i 部分，左括号比右括号多 j 个的所有方案的集合(即不同数量的左括号的方案数)

(2)属性：数量

状态计算：

(1) 若str[i] == '('，易推算出转移方程为f[i][j] = f[i - 1][j - 1]

(2) 若str[i] == ')'，则在只考虑前 i - 1部分时，此时左括号数量最多比右括号多 j + 1个，才可能在第 i 部分通过添加或者不加左括号，达到左括号的数量比右括号多 j 个，故状态转移方程为f[i][j] = f[i - 1][j + 1] + f[i - 1][j] + ...... + f[i - 1][0]，通过完全背包的思维优化这一段转移方程，使得该部分总复杂度由 O(n^3) 降为O(n^2)，优化的状态转移方程为f[i][j] = f[i - 1][j + 1] + f[i][j - 1] (为了防止越界，f[i][0]需要特判)。

CODE

#python3
MOD = (int)(1e9 + 7)

def add(x, y):  
    return (x + y) % MOD

def brackets():
    f = [[0 for i in range(n + 10)] for i in range(n + 10)]  
    f[0][0] = 1

    for i in range(1, n + 1):
        if str[i] == '(':
            for j in range(1, n + 1):
                f[i][j] = f[i - 1][j - 1]
        else:
            f[i][0] = add(f[i - 1][0], f[i - 1][1])
            for j in range(1, n + 1):
                f[i][j] = add(f[i - 1][j + 1], f[i][j - 1])

    for i in range(n + 1):
        if f[n][i]:
            return f[n][i]

str = list(input())
n = len(str)

str.insert(0, 0)  //使目标字符串下标从 1 开始
ans_l = brackets()

str.reverse()
for i in range(n):
    if str[i] == '(':
        str[i] = ')'
    else:
        str[i] = '('
str.insert(0, 0)  //使目标字符串下标从 1 开始
ans_r = brackets()

print(ans_l * ans_r % MOD)

//c++
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5010, MOD = 1e9 + 7;

int n;
char str[N];
ll f[N][N];

ll add(ll x, ll y){
    return (x + y) % MOD;
}

ll brackets()
{
    memset(f, 0, sizeof f);
    f[0][0] = 1;

    for (int i = 1; i <= n; i ++ )
        if (str[i] == '('){
            for (int j = 1; j <= n; j ++ ) f[i][j] = f[i - 1][j - 1];
        }
        else{
            f[i][0] = add(f[i - 1][0], f[i - 1][1]);
            for (int j = 1; j <= n; j ++ ) f[i][j] = add(f[i - 1][j + 1], f[i][j - 1]);
        }

    for (int i = 0; i <= n; i ++ )
        if (f[n][i])
            return f[n][i];
    return -1;
}

int main()
{
    scanf("%s", str + 1);
    n = strlen(str + 1);

    ll ans_l = brackets();

    reverse(str + 1, str + n + 1);
    for (int i = 1; i <= n; i ++ )
        if (str[i] == '(') str[i] = ')';
        else str[i] = '(';
    ll ans_r = brackets();

    printf("%lld\n", ans_l * ans_r % MOD);

    return 0;
}