CF629C Famil Door and Brackets 题解

发布于 2021-01-30  467 次阅读


题意

题目链接

给出一个长度为 $m$ 的括号串,在其前后增添字符构造长度为 $n$ 的合法括号串,求方案数。满足 $n-m \le 2000$。

解析

容易发现这是一道 dp 且复杂度基于 $n-m$。

我们已知中间的那条括号串 $S$,需要构造出左边的 $P$ 和右边的 $Q$(当然也可能为空)。通过 dp 方程转移时,考虑需要满足的两个条件,及 '(' 和 ')' 的数量以及前缀。由于对于任何前缀,均满足 '(' 的数量大于等于 ')' 的数量,我们可以定义 $f_{i,j}$ 为 $i$ 个字符,'(' 的数量减去 ')' 的数量为 $j$ 的总方案数。

求出 $f$ 数组后,接着我们可以枚举 $P$ 和 $Q$,考虑他们所需要满足的条件。

  • 如果 $S$ 中有一段前缀 ')' 比 '(' 多,那么 $P$ 显然是需要弥补的(即 '(' 要比 ')' 多),而所最少需要弥补的数量就为 ')' 比 '(' 多最多的那个前缀。
  • $P$ 和 $S$ 总的 '(' 的数量减去 ')' 的值不能比 $Q$ 长,这是显然的。

如此我们容易地枚举了 $P$ 和 $Q$,计算贡献显然就是乘法原理。$P$ 的价值显而易见为 $f_{i,j}$,而 $Q$ 的价值为 $f_{n-m-i,j+tmp}$( $tmp$ 为 $S$ 中 '(' 的数量减去 ')' 的值)。为什么呢?我们可以逆向思维,从后往前构筑 $Q$,那么前缀条件的定义就反了一下,也就自然得到了这个式子,应当可以自行理解。

将每组的 $P$ 和 $Q$ 的贡献乘起来再累加即可得到答案

代码

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2050;
const int M=2e5+5;
const int mod=1e9+7;    
int n,m,f[N][N],minn,ans,tmp;//f 表示 i 个字符,j=num'(' - num')'
char s[M];
signed main(){
    scanf("%lld%lld",&n,&m);
    scanf("%s",s+1);
    f[0][0]=1; 
    for(int i=1;i<=2000;i++){//保证前缀和满足的情况下的方案数 
        f[i][0]=f[i-1][1];
        for(int j=1;j<=i;j++){
            f[i][j]=(f[i-1][j-1]+f[i-1][j+1])%mod;
        }
    }
    for(int i=1;i<=m;i++){//统计右括号最多比左括号多的,左边要补;
        if(s[i]=='(') tmp++;//以及 num'(' - num')'   
        else tmp--;
        minn=min(tmp,minn);
    }
    for(int i=0;i<=n-m;i++){
        for(int j=0;j<=i;j++){
            if(j+minn>=0&&j+tmp<=n-m-i){//左边及给出的串保证前缀符合且前缀不会大到右边补不回来 
                ans=(ans+(f[i][j]*f[n-m-i][j+tmp])%mod)%mod;//逆向思维 
            }
        }
    }
    printf("%lld\n",ans); 
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣