//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
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
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 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|
常用链接
留言簿(2)
随笔分类
随笔档案
搜索
最新评论
阅读排行榜
评论排行榜
|
|