[COCI2007-2008#1] ZAPIS 题解
OccDreamer
·
·
题解
题目传送门
前置知识
区间型动态规划
思考过程
这题也算是一道很经典的问题了（？）。
看见 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 匹配。这样便可以符合要求。
举个例子来更好地了解这个过程。
拿样例 $1$ 来解释。
在计算 $dp(1,6)$ 时，只有 $p=2$ 对其产生了贡献，而 $p=4$ 时，$dp(2,3)=0$ 故并没有产生贡献。
## 实现
实现有一个细节，就是答案大于等于 $10^5$ 时，需要补上前导 $0$。
```cpp
#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;
}
```