AOJ2035 It Prefokery Pio

問題

文字列から部分列を取り出し、最長の回文を作れ。複数ある場合はそのうち1つを出力せよ。

解答

区間DPをする。

一致していたらを進めてを縮める。不一致ならを進めた場合とを縮めた場合の両方を試して大きい方を採用する。復元のために、状態に対して使った遷移をと記憶しておく。復元パートは、初めからはじめて、使った遷移に沿って長さを最大した経路をなぞれば良い。

#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i,n) repi(i,0,n)
 
string S;
int dp[2222][2222];
int trans[2222][2222];

int rec(int L, int R) {
  int& ret = dp[L][R];
  int& recons = trans[L][R];
  if(ret + 1) return ret;
  if(L > R) return ret = 0;
  if(S[L] == S[R]) {
    recons = 0;
    return ret = rec(L + 1, R - 1) + (L == R ? 1 : 2);
  }
 
  int r1 = rec(L + 1, R);
  int r2 = rec(L, R - 1);
 
  if(r1 > r2) {
    recons = 1;
    return ret = r1;
  }
  else {
    recons = 2;
    return ret = r2;
  }
 
}
 
int main() {
  while(cin >> S) {
 
    for(int i=0; i<2222; i++)
      for(int j=0; j<2222; j++)
        dp[i][j] = trans[i][j] = -1;
 
    int N = S.size();
    rec(0, N);
    int L = 0, R = N;
    string res;
    while(L < R) {
      if(trans[L][R] == 0) res += S[L], L ++, R --;
      if(trans[L][R] == 1) L ++;
      if(trans[L][R] == 2) R --;
    }
    cout << res;
    if(L == R) cout << S[L];
    reverse(res.begin(), res.end());
    cout << res << endl;
  }
  return 0;
}