UVa 11151 : Longest Palindrome

UVa演習 2014/6/24 (火) 問2

問題リンク : http://uva.onlinejudge.org/external/111/11151.html

問題概要 :
文字列が与えられる
文字列から余計な文字を削除して良いのでそこから得られる最長の回文の長さをもとめよ

解法：
メモ化再帰
両端を決めてどちらを削除するかで探索
空の行が入力としてくるのでgetlineで入力をとること

コード：

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

string s;
int memo[1010][1010];
int dfs(int L,int R){

  if( memo[L][R] >= 0 ) return memo[L][R];
  if( L >= R ) return L == R;
  if( s[L] == s[R] ) return memo[L][R] = (dfs(L+1,R-1)+2);
  return memo[L][R] = max(dfs(L+1,R),dfs(L,R-1));
}

int main(){
  int T;
  cin >> T;
  cin.ignore();
  while( T-- ){
    getline(cin,s);
    int n = s.size();
    rep(i,n+1) rep(j,n+1) memo[i][j] = -1;
    cout << dfs(0,n-1) << endl;
  }
  return 0;
}