Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
果然,我也是少一個\n就WA。。。服了这题In Reply To:WA的童鞋 ,别忘了"\n",血得教训 Posted by:fengyuehan at 2011-08-17 16:57:43 #include <iostream> #include <stdio.h> #include <cstring> using namespace std; int val[110][110] = {0}; int trace[110][110]; char brackets[110] = {'\0'}; void print(int i, int j){ if(i > j) return; if(i == j){ if(brackets[i] == '(' || brackets[i] == ')') printf("()"); else printf("[]"); return; } if(trace[i][j] == -1){ print(i,i); print(i+1, j); return; } int k = trace[i][j]; printf("%c", brackets[i]); print(i+1, k-1); printf("%c", brackets[k]); print(k+1, j); } int main() { scanf("%s", brackets); int len = strlen(brackets); for(int i = 0; i < len; i++){ val[i][i] = 1; } for(int cha = 1; cha <= len-1; cha ++){ for(int i = 0; i < len-cha; i++){ int j = i + cha; if(brackets[i] == ')' || brackets[i] == ']') { val[i][j] = val[i+1][j] + 1; trace[i][j] = -1; } if(brackets[i] == '('){ int value = val[i+1][j] + 1; int arg = -1; for(int k = i+1; k <= j; k++){ if(brackets[k] != ')') continue; int tempval = val[i+1][k-1] + val[k+1][j]; if(tempval < value){ arg = k; value = tempval; } } val[i][j] = value; trace[i][j] = arg; } if(brackets[i] == '['){ int value = val[i+1][j] + 1; int arg = -1; for(int k = i+1; k <= j; k++){ if(brackets[k] != ']') continue; int tempval = val[i+1][k-1] + val[k+1][j]; if(tempval < value){ arg = k; value = tempval; } } val[i][j] = value; trace[i][j] = arg; } } } //cout << val[0][len-1] << endl; print(0, len-1); printf("\n"); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator