前置知识
思考过程
这题也算是一道很经典的问题了（？）。
看见 \(n \leq 200\)，不难想到复杂度为 \(O(n^3)\) 的区间型动态规划。
题面中有这么一段话。
- 空串是规则括号序列。
- 如果 \(\texttt A\) 是规则括号序列，那么 \(\texttt{(A) [A] {A}}\) 都是规则括号序列。
- 如果 \(\texttt A,\texttt B\) 都是规则括号序列，那个序列 \(\texttt {AB}\) 也是规则括号序列。
这相当于直接告诉了我们动态规划的转移方程。
设 \(dp(l,r)\) 表示由 \([l,r]\) 之间的字符组成的字符串有多少种不同的括号序列。
定义函数 \(g(i,j)\) 表示第 \(i\) 个字符与第 \(j\) 个字符可以组成多少对不同的括号。
- 对于空串而言，令 \(dp(l,l-1)=1\)。
- 对于 \(\texttt{(A)}\) 这一类的括号序列，可以写出转移方程 \(dp(l,r)\leftarrow dp(l,r)+g(l,r)\times dp(l+1,r-1)\)。
- 对于 \(\texttt{AB}\) 类型的接下来我们重点讨论。
思路 \(1\)
我们能不能直接枚举一个位置 \(p\)，写出转移方程 \(dp(l,r) \leftarrow dp(l,r) + \sum_{p=l+1}^{r-1} dp(l,p) \times dp(p+1,r)\)。
经过思考不难发现这样是不行的，通过样例 \(1\) 就可以发现。
如果按照上述思想，\(dp(1,6)=dp(1,4) \times dp(5,6) +dp(1,2) \times dp(3,6)=2\)，但是答案是 \(1\)。
这个转移错就错在重复计算了答案。
思路 \(2\)
沿用思路 \(1\)，既然知道问题出在哪，那么我们思考一下应该如何解决。
算重就是因为存在两个位置 \(p_1,p_2\)，满足 \([p_1,p_2]\) 构成合法的括号序列。
那么应该怎么解决呢？解决问题的关键就在于在转移的过程中不存在 \(p_1,p_2\) 两个转移点使得 \([p_1,p_2]\) 被重复计算贡献。
考虑强制要求由 \([l,p]\) 构成的合法括号序列 \(l,p\) 匹配。这样便可以符合要求。
\(dp(l,r)\leftarrow dp(l,r)+\sum_{p=l+1}^{r-1} g(l,p) \times dp(l+1,p-1) \times dp(p+1,r)\)。
举个例子来更好地了解这个过程。
拿样例 \(1\) 来解释。
在计算 \(dp(1,6)\) 时，只有 \(p=2\) 对其产生了贡献，而 \(p=4\) 时，\(dp(2,3)=0\) 故并没有产生贡献。
实现
实现有一个细节，就是答案大于等于 \(10^5\) 时，需要补上前导 \(0\)。
#include<bits/stdc++.h>
#define int long long
#define RI register int
#define ll long long
using namespace std;
namespace IO{
inline int read(){
RI X=0, W=0;register char ch=getchar();
while(!isdigit(ch)) W|=ch=='-', ch=getchar();
while(isdigit(ch)) X=(X<<1)+(X<<3)+(ch^48), ch=getchar();
return W?-X:X;
}
inline void write(int x){
if(x<0) x=-x, putchar('-');
if(x>9) write(x/10);
putchar(x%10+'0');
}
}using namespace IO;
const int MAXN = 205;
const int mod = 1e5;
int n;
int dp[MAXN][MAXN];
int br[MAXN];
bool mark[MAXN][MAXN];
char s[MAXN];
inline int match(int x, int y){
if(br[x]==0 && br[y]>0) return 1;
if(br[y]==0 && br[x]<0) return 1;
if(br[x]<0 && br[x]+br[y]==0) return 1;
if(br[x]==br[y] && br[x]==0) return 3;
return 0;
}
signed main(){
n=read();scanf("%s",s+1);
for(int i=1;i<=n+1;++i) dp[i][i-1]=1;
for(int i=1;i<=n;++i){
if(s[i]=='?') br[i]=0;
if(s[i]=='(') br[i]=-1;
if(s[i]==')') br[i]=1;
if(s[i]=='[') br[i]=-2;
if(s[i]==']') br[i]=2;
if(s[i]=='{') br[i]=-3;
if(s[i]=='}') br[i]=3;
}
for(int len=2;len<=n;len+=2){
for(int i=1, j;i+len-1<=n;++i){
j=i+len-1;
dp[i][j]=dp[i+1][j-1]*match(i,j);
if(dp[i+1][j-1]*match(i,j)) mark[i][j]|=mark[i+1][j-1];
if(dp[i][j]>=mod) dp[i][j]-=mod;
for(int p=i+1;p<j;p+=2){
dp[i][j]+=(1ll*dp[i+1][p-1]*dp[p+1][j]*
match(i,p));
if(1ll*dp[i+1][p-1]*dp[p+1][j]*match(i,p)) mark[i][j]|=mark[i+1][p-1]|mark[p+1][j];
if(dp[i][j]>=mod) mark[i][j]=1, dp[i][j]%=mod;
}
}
}
if(mark[1][n]){
int tot=0, ans[20];
while(dp[1][n]) ans[++tot]=dp[1][n]%10, dp[1][n]/=10;
for(int i=5;i>tot;--i) write(0);
for(int i=tot;i>=1;--i) write(ans[i]);
putchar(10);
}
else write(dp[1][n]);
return 0;
}