PKU 2955 Brackets

http://poj.org/problem?id=2955
与えられた入力から括弧の整合性が取れるように、部分列を取り出す時、最も長いものの長さを答えろというような問題。

メモ化再帰しました。

string in;

int memo[200][200];
int vis[200][200];

int rec(int s,int e){
  if(s+1>=e)return 0;
  if(vis[s][e])return memo[s][e];
  vis[s][e]=true;
  int&ret=memo[s][e]=0;
  if(in[s]=='(' && in[e-1]==')' ||
     in[s]=='[' && in[e-1]==']')ret=2+rec(s+1,e-1);

  for(int mi=s+1;mi<e;++mi)
    ret=max(ret,rec(s,mi)+rec(mi,e));
  return ret;
}

void solve(){
  memset(vis,0,sizeof(vis));
  cout<<rec(0,SZ(in))<<endl;
}

main(){
  while(cin>>in,in[0]!='e')solve();
}