UVa 10453 : Make Palindrome

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

問題リンク : http://uva.onlinejudge.org/external/104/10453.html

問題概要 :
文字列が与えられる
その文字列の任意の場所に任意の文字を任意の数だけ追加できる
追加の回数を最小にして回文を作成せよ
そのときの最小の追加回数とそうしてできる回文のうちどれか１つを出力せよ

解法：
メモ化再帰と経路復元
メモ化再帰の際に、どちら側に文字を追加したかを記録することで後々文字列を復元できる

コード:

#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;

const int IINF = INT_MAX;
string s;
int memo[1010][1010];
int path[1010][1010];

// L:-1 0 R:1
int dfs(int L,int R){

  if( memo[L][R] != IINF ) return memo[L][R];
  if( L >= R ) return 0;
  if( s[L] == s[R] ) {
    path[L][R] = 0;
    return memo[L][R] = dfs(L+1,R-1);
  }
  int res1 = dfs(L+1,R)+1;
  int res2 = dfs(L,R-1)+1;
  if( res1 < res2 ){
    path[L][R] = -1;
  } else {
    path[L][R] = 1;
  }
  return memo[L][R] = min(res1,res2);
}

int main(){
  while( getline(cin,s) ){
    int len = s.size();
    rep(i,len+1) rep(j,len+1) memo[i][j] = path[i][j] = IINF;
    int mini = dfs(0,len-1);
    cout << mini << ' ';
    deque<char> deq[2];
    int x=0,y=len-1;
    while( path[x][y] != IINF ){

      if( path[x][y] == 0 ) {
        assert( s[x] == s[y] );
        deq[0].push_back(s[x]);
        deq[1].push_front(s[y]);
        x++,y--;
      } else if( path[x][y] < 0 ) {
        deq[0].push_back(s[x]);
        deq[1].push_front(s[x]);
        x++;
      } else {
        deq[0].push_back(s[y]);
        deq[1].push_front(s[y]);
        y--;
      }
    }
    if( x == y ) deq[0].push_back(s[x]);
    rep(i,deq[0].size()) cout << deq[0][i];
    rep(i,deq[1].size()) cout << deq[1][i];
    cout << endl;
  }
  return 0;
}