|
|
back to boardHelp! WA at #13, Why? I use memoization to solve the promblem, but WA#13. I have no idea about it(although I've been debugging for 2 days). Can you help me? Here's the code: #include <iostream> #include <fstream> #include <string> #include <cassert> using namespace std; ifstream fin("bracket.in"); ofstream fout("bracket.out"); string S; inline bool isregular(int i,int j) { if(j<i) return true; else if(j==i) return false; char stack[100]; int p=0; for(int k=i;k<=j;k++) { if(p==0) { if(S[k]=='('||S[k]=='[') stack[p++]=S[k]; else return false; } else{ if(( stack[p-1]=='('&&S[k]==')' )||( stack[p-1]=='['&&S[k]==']' )) p--; else if(S[k]==')'||S[k]==']') return false; else stack[p++]=S[k]; } } return (p==0); } string s[100][100]; string memo(int i, int j) { if(s[i][j]!="") return s[i][j]; if(isregular(i,j)) { s[i][j].assign(S,i,j-i+1); return s[i][j]; } if(i==j) { if(S[i]=='('||S[i]==')') s[i][j]="()"; else if(S[i]=='['||S[i]==']') s[i][j]="[]"; else assert(0); return s[i][j]; } string ans,tmp,tmp2; unsigned size=UINT_MAX; if(( S[i]=='('&&S[j]==')' )||( S[i]=='['&&S[j]==']' )) { ans=S[i]+memo(i+1,j-1)+S[j]; size=ans.size(); } else if(( S[i]=='('&&S[j]!=')' )||( S[i]=='['&&S[j]!=']' )) { ans=S[i]+memo(i+1,j); if(S[i]=='(') ans=ans+')'; else if(S[i]=='[') ans=ans+']'; else assert(0); size=ans.size(); } else if(( S[i]!='('&&S[j]==')' )||( S[i]!='['&&S[j]==']' )) { ans=memo(i,j-1)+S[j]; if(S[j]==')') ans='('+ans; else if(S[j]==']') ans='['+ans; else assert(0); size=ans.size(); } for(int k=i;k<j;k++) if(size>memo(i,k).size()+memo(k+1,j).size()) { ans=memo(i,k)+memo(k+1,j); size=memo(i,k).size()+memo(k+1,j).size(); } return (s[i][j]=ans); } int main() { cin >> S; cout << memo(0,S.size()-1) << endl; return 0; } Edited by author 23.05.2007 16:19 Re: Help! WA at #13, Why? Problem found. This program crashes when the input string is empty. ----author |
|
|