括号序列-紫书题解

题目链接：https://uva.onlinejudge.org/external/16/1626.pdf
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int d[100][100],n;
char s[101];
int match(char a,char b){
    return (a == '[' && b == ']') || (a == '(' && b == ')');
}
void dp(){
    for(int i=0;i<n;i++){
        d[i+1][i]=0;
        d[i][i]=1;
    }
    for(int i=n-2;i>=0;i--){
        for(int j=i+1;j<n;j++){
            d[i][j]=n;
            if(match(s[i],s[j]))    d[i][j] = min(d[i][j],d[i+1][j-1]);
            for(int k=i;k<j;k++){
                d[i][j]=min(d[i][j],d[i][k]+d[k+1][j]);
            }
        }
    }
}
void print(int i,int j){
    if(i>j) return ;
    if(i == j){
        if(s[i] == '[' || s[i] == ']') printf("[]");
        else printf("()");
        return ;
    }
    int ans = d[i][j];
    if(match(s[i],s[j]) && ans == d[i+1][j-1]){
        printf("%c",s[i]);
        print(i+1,j-1);
        printf("%c",s[j]);
        return ;
    }
    for(int k=i;k<j;k++)
        if(ans == d[i][k]+d[k+1][j]){
            print(i,k); print(k+1,j);
            return ;
        }
}
int main(void){
    gets(s);
    n = strlen(s);
    dp();
    cout<<d[0][n-1]<<endl;
    print(0,n-1);
    return 0;
}