配对括号

· · 个人记录

题目

Hecy 又接了个新任务：BE 处理。BE 中有一类被称为 GBE。

以下是 GBE 的定义：

1.空表达式是 GBE

2.如果表达式 A是 GBE，则 [A] 与 (A) 都是 GBE

3.如果 A 与 B 都是 GBE，那么 AB 是 GBE

给出一个 BE，求至少添加多少字符能使这个 BE 成为 GBE。

解析

这道题可以用动态规划来解决

所以我们需要定义一下几个东西:废话

过程：好像什么都没说

首先读入字符串并计算其长度。然后初始化状态数组 f[i][i] 的值为 1，表示长度为 1 的子串需要插入 1 次才能变成合法的括号序列。接下来使用两层循环枚举所有可能的子串长度和起始位置，并调用函数 dp 进行状态转移。最后输出结果 f[1][n] 即可。

函数ch大家一定也都知道是用于判断两个字符是否是匹配的括号

然后就是最重要的函数dp：

它接受两个参数 i 和 j，表示当前处理的子串的起始位置和结束位置。函数内部首先使用一个循环枚举子串中所有可能的分割点 k，并根据状态转移方程更新状态数组 f[i][j] 的值。然后判断子串两端的字符是否为一对匹配的括号，如果是，则根据状态转移方程更新状态数组 f[i][j] 的值。

状态转移方程：

对于区间 [i,j]，如果 a[i] 和 a[j] 匹配，即一个左括号和一个右括号匹配，那么我们可以通过在 i+1 到 j-1 区间内构成一个合法括号序列，然后再在左右两侧加上括号来使得区间 [i,j] 变成一个合法的括号序列，此时的最小插入操作次数为 f[i+1][j-1]。

而当 a[i] 和 a[j] 不匹配时，我们可以通过枚举区间 [i,k] 和 [k+1,j]，使它们变为合法的括号序列，然后再将它们合并起来形成一个新的合法括号序列，此时的最小插入操作次数为 f[i][k] + f[k+1][j]，其中 k 的范围从 i 到 j-1。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
char a[110];
int f[110][110];
int n;
bool ch(char a,char b){//判断两个字符是否是匹配的括号
    if(a=='('&&b==')') return 1;
    if(a=='['&&b==']') return 1;
    return 0;
}
void dp(int i,int j){
    for(int k=i;k<=j;k++)
        f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
   //枚举子串中所有可能的分割点k，并根据状态转移方程更新
    if(ch(a[i],a[j])) f[i][j]=min(f[i][j],f[i+1][j-1]);
   //如果是，则根据状态转移方程更新状态数组f[i][j]的值
} 
int main(){
    scanf("%s",a+1);
    n=strlen(a+1);//计算字符串a的长度
    for(int i=1;i<=n;i++)
//初始化f数组的对角线元素为1，表示单个字符需要添加一个括号才能匹配
        f[i][i]=1;
    for(int len=2;len<=n;len++)
        for(int i=1;i+len-1<=n;i++){//枚举所有可能的子串长度和起始位置
            int j=i+len-1;
            f[i][j]=0x7fffffff;//初始化为一个很大的数，表示最初没有找到合适的方案
            dp(i,j);
        }
    printf("%d",f[1][n]);//完成撒花
    return 0;
}