uva 1626 添加最少的括号使得括号匹配

桃扇骨 2022-08-03 13:42 75阅读 0赞

添加最少的括号使得括号匹配，并将括号匹配后的结果输出，可能有空串，所以输入的时候要用gets（）；

#include<map>
    #include<vector>
    #include<cstdio>
    #include<iostream>
    #include<cstring>
    #include<string>
    #include<algorithm>
    #include<cmath>
    #include<stack>
    #include<queue>
    #include<set>
    #define inf 0x3f3f3f3f
    #define mem(a,x) memset(a,x,sizeof(a))
    
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    inline int in()
    {
        int res=0;char c;
        while((c=getchar())<'0' || c>'9');
        while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
        return res;
    }
    char a[111];
    int dp[111][111];
    int c[111][111];//记录从哪里断开
    
    bool match(char a,char b)
    {
        if(a=='(' && b==')')return 1;
        if(a=='[' && b==']')return 1;
        return 0;
    }
    
    void print(int i,int j)
    {
        if(i>j)return;
        if(i==j)
        {
            if(a[i]=='(' || a[i]==')')putchar('('),putchar(')');
            else putchar('['),putchar(']');
        }
        else
        {
            if(c[i][j]>=0)
            {
                print(i,c[i][j]);
                print(c[i][j]+1,j);
            }
            else
            {
                if(a[i]=='(')
                {
                    putchar('(');
                    print(i+1,j-1);
                    putchar(')');
                }
                else
                {
                    putchar('[');
                    print(i+1,j-1);
                    putchar(']');
                }
            }
        }
    }
    
    int main()
    {
        int T=in();
        while(T--)
        {
            gets(a);//开始有个空行
            gets(a);
            mem(c,-1);
            int n=strlen(a);
            if(n==0)//处理空串
            {
                puts("");
                if(T)puts("");
                continue;
            }
            for(int i=0;i<n;i++)
            {
                dp[i][i]=1;
            }
            for(int len=2;len<=n;len++)//枚举括号的长度
            {
                for(int i=0;i+len<=n;i++)//枚举括号开始的位置i
                {
                    int j=i+len-1;      //结束位置
                    dp[i][j]=dp[i][i]+dp[i+1][j]; //初始化
                    c[i][j]=i;
                    for(int k=i+1;k<=j-1;k++)   //从子结构中选择最小的
                    {
                        if(dp[i][j]>dp[i][k]+dp[k+1][j])
                        {
                            dp[i][j]=dp[i][k]+dp[k+1][j];
                            c[i][j]=k;              //从k处断开
                        }
                    }
                    if(match(a[i],a[j]))          //如果i跟j匹配 dp[i][j]=min（dp[i+1][j-1],dp[i][j]）;
                    {
                        if(i+1==j)dp[i][j]=0,c[i][j]=-1;
                        else if(dp[i][j]>dp[i+1][j-1])  
                        {
                            dp[i][j]=dp[i+1][j-1];
                            c[i][j]=-1;
                        }
                    }
                }
            }
    
            print(0,n-1);
            puts("");
            if(T)puts("");
        }
        return 0;
    }