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

AOJ2035 It Prefokery Pio

問題

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

解答

区間DPをする。

dp[L][R]\ :=\ 位置[L,\ R)で最長の回文の長さ trans[L][R]\ :=\ 位置[L,\ R)において最長の回文を生成するために使った遷移

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

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