問題 C - [ [ iwi ] ]
http://atcoder.jp/problem/detail/27
124(28)分で正解
LCSです。
iwiは必ず出現し、かつ、作る部分列も1度はiwiを含まなければならない
というのを見落としてて1WA
iwiは1度しか出現しないので、部分文字列iwiの位置を調べて、
手前と後ろで文字列を分ける。
線対称に対応させるために片方の文字列を反転させたものをLCS処理
int dp[32][32]; int ok(char a, char b){ if( a=='(' ){ return (b==')'); }else if( a==')' ){ return (b=='('); }else if( a=='{' ){ return (b=='}'); }else if( a=='}' ){ return (b=='{'); }else if( a=='[' ){ return (b==']'); }else if( a==']' ){ return (b=='['); }else{ return (a==b); } } int main(){ string str; while(cin>>str){ memset(dp,0,sizeof(dp)); int p = str.find("iwi"); string s1 = str.substr(0,p); string tmp = str.substr(p+3); string s2 = string(tmp.rbegin(), tmp.rend()); int n = s1.length(); int m = s2.length(); REP(i,1,n+1){ REP(j,1,m+1){ dp[i][j] = max(dp[i-1][j-1]+ok(s1[i-1],s2[j-1]), max(dp[i-1][j], dp[i][j-1])); } } printf("%d\n",dp[n][m]*2 + 3); } return 0; }