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(); }