POJ1141
#include <iostream>
using namespace std;
const int MAXN = 110;
char str[MAXN] ;
int dp [MAXN][MAXN];
int path[MAXN][MAXN];
int output( int i, int j){
if(i>j)
return 0 ;
if(i==j){
if(str[i]=='('||str[i]==')')
cout<<'('<<')';
else if(str[i]=='['||str[i]==']')
cout<<'['<<']';
return 0;
}
if(path[i][j]==-1){
cout<<str[i];
output(i+1, j-1);
cout<<str[j];
}
else {
output(i, path[i][j]);
output(path[i][j]+1, j);
}
return 0;
}
int main() {
int n, len, i, j,k,r;
while(gets(str)){
n = strlen(str);
if(n==0){
printf("\\n");
continue;
}
memset(dp,0,sizeof(dp));
for( i = 0; i<n;i++){
dp[i][i] = 1;
}
for( len = 1;len< n;len++){
for( i = 0; i<n-len;i++){
j = i+len;
dp[i][j]=INT_MAX;
if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']')){
if(dp[i][j]>dp[i+1][j-1]){
dp[i][j] = dp[i+1][j-1];
path[i][j] = -1;
}
}
for( k = i;k<j;k++){
if(dp[i][k]+dp[k+1][j]<dp[i][j]){
dp[i][j] = dp[i][k]+dp[k+1][j];
path[i][j]= k;
}
}
}
}
output( 0, n-1);
printf("\\n");
}
return 0;
}
char * gets ( char * str );
size_t strlen ( const char * str );
void * memset ( void * ptr, int value, size_t num );
//Sets the first num bytes of the block of memory pointed by ptr to the specified value (interpreted as an unsigned char)
posted on 2011-03-20 10:54
sweet empyrean 阅读(125)
评论(0) 编辑 收藏 引用 所属分类:
POJ