[DP]JZOJ 5804 简单的序列

Description

从前有个括号序列 s，满足 |s| = m。你需要统计括号序列对 (p, q) 的数量。
其中 (p, q) 满足 |p| + |s| + |q| = n，且 p + s + q 是一个合法的括号序列。

 

Input

从文件 bracket.in 中读入数据。第一行两个正整数 n, m。
第二行一个长度为 m 的括号序列，表示 s。
 

Output

输出到文件 bracket.out 中。
输出一行一个整数，表示符合条件的 (p, q) 的数量对 10^9 + 7 取模的值。
 
 

 

Sample Input

【样例 1 输入】
4 1 (
【样例 2 输入】
4 4 (())
【样例 3 输入
4 3 (((
 

Sample Output

【样例 1 输出】
4
【样例 2 输出】
1
【样例 3 输出】
0
 

 

Data Constraint

对于 10% 的数据，n ≤ 20；
对于 25% 的数据，n ≤ 200；
对于另外 5% 的数据，n = m；
对于 55% 的数据，n − m ≤ 200；
对于 100% 的数据，1 ≤ m ≤ n ≤ 10^5, n − m ≤ 2000。

分析

设一个DP为f[i][j]表示q串长度为i时，左右括号之和（一个1一个-1）为j时的方案数，显然最终答案为f[i][j]*f[n-m-i][j+lenofs]的和

#pragma GCC optimize(2)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const long long P=1e9+7;
int n,m;
char c[100001];
int s[100001],mins;
long long f[2001][2002];

int main() {
    freopen("bracket.in","r",stdin);
    freopen("bracket.out","w",stdout);
    scanf("%d%d",&n,&m);
    scanf("%s",c);
    int len=strlen(c);mins=2147483647;
    for (int i=1;i<=len;i++) {
        s[i]=s[i-1]+(c[i-1]=='('?1:-1);
        mins=min(mins,s[i]);
    }
    f[0][0]=1;
    for (int i=1;i<=n-m;i++)
    for (int j=0;j<=i;j++) {
        if (j) f[i][j]+=f[i-1][j-1];
        f[i][j]%=P;
        f[i][j]+=f[i-1][j+1];
        f[i][j]%=P;
    }
    long long ans=0; 
    for (int i=0;i<=n-m;i++)
    for (int j=0;j<=i;j++)
    if (j+s[len]<=n-m&&j+mins>=0) ans=(ans+f[i][j]*f[n-m-i][j+s[len]]%P)%P;
    printf("%lld",ans);
    fclose(stdin);fclose(stdout);
}