括号序列

Uva 1626，括号序列

 

题目链接：https://uva.onlinejudge.org/external/16/1626.pdf

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int f[100][100],n;
char s[100];
void print(int x,int y){
    if(x == y){
        if(s[x] == '[' || s[x] == ']')
            cout<<"[]";
        if(s[x] == '(' || s[x] == ')')
            cout<<"()"; 
    }
    else if(f[x][y] == 0){ 
        for(int i=x;i<=y;i++)
            cout<<s[i]; 
    }
    else if((s[x] == '[' && s[y] == ']') || (s[x] == '(' && s[y] == ')') && f[x+1][y-1] == f[x][y]){
        cout<<s[x];
        print(x+1,y-1);
        cout<<s[y];
    } 
    else {

        for(int k=x;k<y;k++)
            if(f[x][k]+f[k+1][y] == f[x][y]){
                print(x,k);
                print(k+1,y);
                break;
            }
    }
} 
int main(void){
    gets(s+1);
    int length = strlen(s+1);
    if(length == 0){
        cout << 0 <<endl;
    }
    else{
        for(int i=1;i<=length;i++)
            for(int j=i;j<=length;j++)
                f[i][j]=j-i+1;
        for(int len=2;len<=length;len++)
            for(int i=1;i<=length-len+1;i++){
                int j=i+len-1;
                if((s[i] == '[' && s[j] == ']') || (s[i] == '(' && s[j] == ')'))
                    f[i][j] = f[i+1][j-1];
                for(int k=i;k<j;k++)
                    f[i][j] = min(f[i][j],f[i][k]+f[k+1][j]);
            }
        cout << f[1][length] << endl;
    }
    if(length)
        print(1,length);
    return 0;
}