//edited by Eddy
//from BeiHang Univ
//any questions,contact oeddyo@gmail.com

#include <iostream>
using namespace std;
#define MAX 101

int res[MAX][MAX];
int pos[MAX][MAX];

void output(char a[],int b,int e)
  {
if(b>e)
return ;
if(pos[b][e]==-1)
 {
cout<<a[b];
output(a,b+1,e-1);
cout<<a[e];
return ;
}
if(b==e)
 {
if(a[b]=='('||a[e]==')')
cout<<"()";
else if(a[b]=='['||a[e]==']')
cout<<"[]";
return ;
}
output(a,b,pos[b][e]);
output(a,pos[b][e]+1,e);
}

int main()
  {
char s[120];
while(cin.getline(s,101))
 {
memset(res,0,sizeof(res));
memset(pos,0,sizeof(pos));
int s_size=strlen(s);

for(int i=0;s[i];i++)
 {
res[i][i]=1;
for(int j=i-1; j>=0; j--)
 {
if(s[j]=='('&&s[i]==')'||s[j]=='['&&s[i]==']')
 {
res[j][i]=res[j+1][i-1];
pos[j][i]=-1; //标记-1即不用多补
}
else
 {
res[j][i]=10000000;
}

for(int k=j;k<i;k++) //经典代码。。。多理解
 {
int t=res[j][k]+res[k+1][i];
if(t<res[j][i])
 {
res[j][i]=t;
pos[j][i]=k;
}
}

}
}
output(s,0,s_size-1);
cout<<endl;
}
return 0;
}

|
|
随笔:10
文章:0
评论:3
引用:0
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
25 | 26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
常用链接
留言簿(2)
随笔分类
随笔档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|