#include<iostream>
#include<stdlib.h>
using namespace std;
int ar[101],f[101][101],v[101][101];
string s;
int outar[201],count1;
int work(int b,int e)
{
    if(b>e)return 0;
    if(b==e){outar[++count1]=-abs(ar[b]);outar[++count1]=abs(ar[b]);return 0;}
    int i;
    if(v[b][e]==-1)
    {
       outar[++count1]=ar[b];
       work(b+1,e-1);
       outar[++count1]=ar[e];
       return 0;
    }
    else 
    {
           work(b,v[b][e]);
           work(v[b][e]+1,e);
           return 0;
    }
}
int main()
{
    //freopen("poj1141.in","r",stdin);
    //freopen("poj1141.out","w",stdout);
    int m,n;
    int i,j,k;
    cin>>s;
    n=s.length();
    for(i=1;i<=n;i++)
    {
       if(s[i-1]=='(')ar[i]=-2;
       if(s[i-1]=='[')ar[i]=-1;
       if(s[i-1]==')')ar[i]=2;
       if(s[i-1]==']')ar[i]=1;
    }
    for(i=1;i<=n;i++)
      f[i][i]=1;
    for(i=1;i<n;i++)
    if(!(ar[i]+ar[i+1]==0&&ar[i]<0))
    {
      f[i][i+1]=2;
      v[i][i+1]=i;
    }
    else 
    {
        f[i][i+1]=0;
        v[i][i+1]=-1;
    }
    for(i=2;i<n;i++)
    {
       for(j=1;j<=n-i;j++)
       {
          if(ar[j]+ar[j+i]==0&&ar[j]<0)
          {
             f[j][j+i]=f[j+1][j+i-1];
             v[j][j+i]=-1;
          }
          else 
          {
             f[j][j+i]=300;
          }
          for(k=j;k<j+i;k++)
          {
              if(f[j][j+i]>f[j][k]+f[k+1][j+i])
              {
                    f[j][j+i]=f[j][k]+f[k+1][j+i];
                    v[j][j+i]=k;
              }
          }
       }
    }
    count1=0;
    work(1,n);
    for(i=1;i<=count1;i++)
    {
       if(outar[i]==-2)cout<<'(';
       if(outar[i]==-1)cout<<'[';
       if(outar[i]==2)cout<<')';
       if(outar[i]==1)cout<<']';
    }
    
}
各种数据都测了，全是对的

• 多组数据？ (2023) kill_myself 2011-04-05 00:10:52