「LOJ10150」括号配对

【题目】

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

以下是 GBE 的定义：

空表达式是 GBE
如果表达式 A 是 GBE，则 [A] 与 (A) 都是 GBE
如果 A 与 B 都是 GBE，那么 AB 是 GBE

样例输入

[])

样例输出

1

【思路】

区间DP

设f[i][j]是区间i~j的最小操作数

方程：f[i][j] = min{f[i][k]+f[k+1][j]}

若a[i] == a[j] f[i][j]=min(f[i][j],f[i+1][j-1]);

代码：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read(){
    char chr = getchar();   int f = 1,ans = 0;
    while(!isdigit(chr)) {if(chr == '-') f = -1;chr = getchar();}
    while(isdigit(chr))  {ans = (ans << 3) + (ans << 1) + chr - '0';chr = getchar();}
    return ans* f ;
}
void write(int x){
    if(x < 0) putchar('-');
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
int f[105][105],n,m;
char a[105];
bool check(char a, char b){
    if(a == '(' && b == ')') return 1;
    if(a == '[' && b == ']') return 1;
    return 0;
}
int main(){
    scanf("%s",a + 1);
    n = strlen(a + 1);
    for(int i = 1;i <= n;i++)
        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]=0x3f3f3f3f;
            for(int k=i;k<=j;k++)
                f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
            if(check(a[i],a[j])) f[i][j]=min(f[i][j],f[i+1][j-1]);
        }
    write(f[1][n]);
    return 0;
}