【DP】【KMP】1015F Bracket Substring

题意：

给出一个括号序列，求包含这个序列的长度为2*n括号匹配的个数。
$|s|\leq 200$
$n\leq 100$

分析：

这里不得不介绍一下BZOJ1009GT考试
这题是简化版本。

很容易发现，这题就是GT问题的补集。

首先，括号匹配的常规DP定义式：$dp(i,j)$表示长度为i，前缀和为j的括号匹配方案数
如果直接DP，是会算重的，因此要将dp加一维，表示成$dp(i,j,k)$表示长度为i，前缀和为j，此时最长能匹配到s串的第k个位置的方案数。

那么为了维护k的转移，我们需要借助kmp算法。

转移式为：
（$qr(k,0)$表示当匹配到第k个位置后，再加入一个字符”(“所匹配到的最远位置，$qr(k,1)$则反之）
$dp(i+1,j+1,qr(k,0))+=dp(i,j,k)$
$dp(i+1,j-1,qr(k,1))+=dp(i,j,k)$

我的方法有点奇怪，我是直接在中途算答案的，并没有算补集。所以下面的内容愿意看就看，不愿意就去写补集吧。

$lasp$表示s串最后一个字符。（“(”为1、“)”为-1）
$dp'(i,j)$表示长度为i，前缀和为j的括号匹配方案数。
当$k=|s|-1$时，$ans+=dp(i,j,k)*dp'(2*n-i-1,k+lasp)$

构建kmp转移我就不赘述了。。。不会的自己去复习kmp

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 210
#define MOD 1000000007
using namespace std;
typedef long long ll;
int n;
char s[MAXN];
ll dp[MAXN][MAXN][MAXN],dp1[MAXN][MAXN];
int mindep,pres,ncnt,len,minl,a[MAXN];
int qr[MAXN][2],las[MAXN];
ll ans;
void build(){len=strlen(s);for(int i=0;i<len;i++){if(s[i]=='(')a[i+1]=0;elsea[i+1]=1;}for(int i=0;i<len;i++){for(int j=0;j<2;j++){int x=i;while(1){if(a[x+1]==j){qr[i][j]=x+1;break;}if(x==0)break;x=las[x];}}int x=i;while(x){x=las[x];if(a[x+1]==a[i+1]){las[i+1]=x+1;break;}}}
}
int main(){SF("%d",&n);SF("%s",s);build();dp[0][0][0]=1;dp1[0][0]=1;for(int i=1;i<=2*n;i++)for(int j=0;j<=i;j++){if(j)dp1[i][j]+=dp1[i-1][j-1];dp1[i][j]+=dp1[i-1][j+1];dp1[i][j]%=MOD;}if(a[len]==0)pres=1;elsepres=-1;for(int i=0;i<=2*n;i++)for(int j=0;j<=i;j++)for(int k=0;k<len;k++){if(j+pres>=0&&k==len-1&&2*n-i-1>=0){//PF("{(%d %d %d %d)%lld %lld}\n",i,j,k,j+pres,dp[i][j][k],dp1[2*n-i-1][j+pres]);ans+=dp[i][j][k]*dp1[2*n-i-1][j+pres];ans%=MOD;}(dp[i+1][j+1][qr[k][0]]+=dp[i][j][k])%=MOD;if(j)(dp[i+1][j-1][qr[k][1]]+=dp[i][j][k])%=MOD;}PF("%lld",ans);
}