読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

問題 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;
}