括号序列

题目

3420. 括号序列 - AcWing题库

给定一个括号序列，要求尽可能少地添加若干括号使得括号序列变得合法，当添加完成后，会产生不同的添加结果，请问有多少种本质不同的添加结果。

两个结果是本质不同的是指存在某个位置一个结果是左括号，而另一个是右括号。

例如，对于括号序列 ((()，只需要添加两个括号就能让其合法，有以下几种不同的添加结果：()()()、()(())、(())()、(()()) 和 ((()))。

输入格式

输入一行包含一个字符串 ss，表示给定的括号序列，序列中只有左括号和右括号。

输出格式

输出一个整数表示答案，答案可能很大，请输出答案除以 $1000000007$(即 $109+7$) 的余数。

数据范围

对于 40% 的评测用例，$|s|≤200$。
对于所有评测用例，$1≤|s|≤5000$。

输入样例：

((()

输出样例：

5

思路

首先我们需要添加的是左括号以及右括号，然后添加的左右括号都是相互独立的。

考虑到我们只能在空隙中添加，能添加左右括号的只有)(这种情况，而()是无效的，相当于自己添加一个左右合法括号，是多此一举，由此可知，我们只需要求出左括号的添加方案数，右括号的添加方案数，两者一乘就是答案。

然后我们以右括号为断点，划分区域，然后忘划分的区域中添加左括号就ok了

$f[i][j]$表示前$i$个右括号，添加$j$个左括号的合法方案数。

那么我们需要预先处理每个区域中至少添加的左括号数量，因为小于该数量，那就不合法了，多了可以在后面进行添加的时候进行修改。

$f[1][i]=1$

转移方程:

$f[i][j]=f[i][j]+f[i-1]k$

进一步优化：

$f[i][j]=f[i-1][0]+f[i-1][1]+…+f[i][j]$

$f[i][j+1]=f[i-1][0]+…+f[i][j]+f[i-1][j+1]$

所以可以得出:

$f[i][j]=f[i][j-1]+f[i-1][j]$

import java.util.*;

public class Main
{
    static StringBuilder s;
    final static int mod = 1000000007;
    static int[][] f = new int[5010][5010];
    static int[] sum = new int[5010];
    static long ans;
    public static int work(int len)
    {
        int lcnt = 0, rcnt = 0, cnt = 0;
        for(int i = 0; i <= len; i ++)
            Arrays.fill(f[i], 0);
        for(int i = 0; i < len; i ++)
        {
            if(s.charAt(i) == '(')
                lcnt ++;
            else
            {
                rcnt ++;
                cnt ++;
                if(lcnt != 0)
                {
                    lcnt --;
                    rcnt --;
                }
                sum[cnt] = rcnt;
            }
        }
        for(int i = sum[1]; i <= len; i ++)
            f[1][i] = 1;
//        for(int i = 2; i <= cnt; i ++)
//        {
//            for(int j = sum[i]; j <= len; j ++)
//                for(int k = 0; k <= j; k ++)
//                    f[i][j] = (f[i][j] + f[i-1][k]) % mod;
//        }
        for(int i = 2; i <= cnt; i ++)
        {
            for(int j = 0; j <= sum[i]; j ++)
                f[i][sum[i]] = (f[i][sum[i]] + f[i - 1][j]) % mod;
            for(int j = sum[i] + 1; j <= len; j ++)
                f[i][j] = (f[i][j - 1] + f[i - 1][j]) % mod;
        }
        return f[cnt][rcnt];
    }
    public static void main(String[] args) {
        Scanner inScanner = new Scanner(System.in);
        s = new StringBuilder(inScanner.next());
        ans = work(s.length());
        for(int i = 0; i < s.length(); i ++)
        {
            if(s.charAt(i) == ')')
                s.setCharAt(i, '(');
            else
                s.setCharAt(i, ')');
        }
        s = s.reverse();
        ans = (ans * work(s.length())) % mod;
        System.out.println(ans % mod);
        inScanner.close();
    }
}
/*
3 3
0 3
1 2
0 2
*/