题意：给你一个由括号组成的字符串，长度为m，现在希望获得一个长度为n（全由括号组成）的字符串,0<=n-m<=2000
这个长度为n的字符串要求有两个性质：1：就是任意前缀，左括号数量大于右括号数量
2：字符串中左括号的数量等于右括号
现在让你可以在长度为m的原串前加一个括号串p,在原串后加一个括号串q 最后p+m+q=n
问有多少种组合p,q能得到目标串
分析：（这题我不会，看了题解才会）
定义dp[i][j],为前缀长为i,且左括号数量-右括号数量=j的串有多少个
所以dp[0][0]=1;
if(j>0)dp[i][j]=dp[i-1][j-1]+dp[i-1][j+1]
else j==0 dp[i][j]=dp[i-1][j+1]
然后处理原串，找到 左-右的最终数量cnt，和最小数量d
然后枚举p的长度和平衡值 对于长度i, 当-d<=j时，p可以加到前面
然后当p确定后，q的长度也确定，因为最终 左=右 ，所以q 的（右-左）的代价也知道了
假设当前是i，平衡度是j,所以只要将dp[i][j]*dp[n-m-i][j+cnt]加到答案就行了
注意：dp[i][j]代表前缀i，平衡度为j的方案数， dp[n-m-i][j+cnt]为后缀n-m-i，平衡度为-(j+cnt)的方案数，是对称的，很重要
#include <cstdio> #include <iostream> using namespace std; typedef long long LL; const int N = 2e3+5; const LL mod = 1e9+7; LL dp[N][N]; char s[100000+5]; int main() { int m,n; scanf("%d%d%s",&n,&m,s+1); dp[0][0]=1; for(int i=1; i<=n-m; ++i) { for(int j=0; j<=i; ++j) { if(!j) dp[i][j]=dp[i-1][j+1]; else dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%mod; } } int cnt=0,d=m+1; for(int i=1; i<=m; ++i) { if(s[i]=='(')++cnt; else --cnt; d=min(d,cnt); } LL ans=0; for(int i=0; i<=n-m; ++i) { for(int j=0; j<=i; ++j) { if(-d<=j&&cnt+j<=n-m-i) ans=(ans+dp[i][j]*dp[n-m-i][cnt+j])%mod; } } printf("%I64d ",ans); return 0; }