【Link】:

【Description】



给你两个括号序列;

让你把这两个括号序列合并起来

(得按顺序合并)

使得组成的新的序列为合法序列;

即每个括号都能匹配;

问有多少种合并的方法;

【Solution】



设f[i][j][k]表示第一个序列取出了前i个括号,第二个序列取出了前j个括号组成的括号序列,且左括号比右括号多了k个的合并方案数;

答案就是f[len1][len2][0]

(且不会有非法的情况,即不会有右括号没被左括号匹配到)

则有转移方式

rep1(i,0,len1)

    rep1(j,0,len2)

        rep1(k,0,50){

            if (i-1>=0){

                if (s1[i]==')'){//从第一个序列拿了一个右括号

                    add(f[i][j][k],f[i-1][j][k+1]);

                }

                if (s1[i]=='(' && k > 0){//从第一个序列拿了一个左括号

                    add(f[i][j][k],f[i-1][j][k-1]);

                }

            }

            if (j-1>=0){

                if (s2[j]==')'){//同理

                    add(f[i][j][k],f[i][j-1][k+1]);

                }

                if (s2[j]=='(' && k > 0){

                    add(f[i][j][k],f[i][j-1][k-1]);

                }

            }

        }

【NumberOf WA】



0



【Reviw】



这种合并的操作,类似每次把两个序列中的一个的开头一个一个加到字符串的末尾;



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 50;

const int MOD = 1e9 + 7;

//head

struct abc{

    int x,id;

};

LL f[N+10][N+10][N+10];

void add(LL &a,LL b){

    a = a+b;

    while (a>=MOD) a -= MOD;

}

class InterleavingParenthesisDiv2

{

    public:

        int countWays(string s1, string s2)

        {

            rep1(i,0,N)

                rep1(j,0,N)

                    rep1(k,0,N)

                        f[i][j][k] = 0;

            int len1 = s1.size(),len2 = s2.size();

            s1 = ' '+s1,s2= ' '+s2;

            f[0][0][0] = 1;

            rep1(i,0,len1)

                rep1(j,0,len2)

                    rep1(k,0,N){

                        if (i-1>=0){

                            if (s1[i]==')'){

                                add(f[i][j][k],f[i-1][j][k+1]);

                            }

                            if (s1[i]=='(' && k > 0){

                                add(f[i][j][k],f[i-1][j][k-1]);

                            }

                        }

                        if (j-1>=0){

                            if (s2[j]==')'){

                                add(f[i][j][k],f[i][j-1][k+1]);

                            }

                            if (s2[j]=='(' && k > 0){

                                add(f[i][j][k],f[i][j-1][k-1]);

                            }

                        }

                    }

            return f[len1][len2][0];

        }

};