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

土下座しながら探索中

主に競技プログラミング

UVa 10739 : String to Palindrome

UVa 回文 メモ化再帰

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

問題リンク : http://uva.onlinejudge.org/external/107/10739.html

問題概要:
長さ1000以下の文字列が与えられる
この文字列のアルファベットに対して以下の3つの操作を自由に使うことができる
・任意の場所に任意のアルファベットを追加する
・任意の場所のアルファベットを削除する
・任意の場所のアルファベットを任意のアルファベットに置換する
与えられた文字列を回文にするために必要な最小の操作の回数を求めよ

解法:
メモ化再帰
UVa 11753の類題

コード:

#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;
char s[1010];
int memo[1010][1010];

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] ) return memo[L][R] = dfs(L+1,R-1);
  int ret = min(dfs(L+1,R)+1,dfs(L,R-1)+1);// add and remove
  ret = min(ret,dfs(L+1,R-1)+1); // Replace
  return memo[L][R] = ret;
}

int main(){
  int T,CNT=1;
  scanf("%d",&T);
  while( T-- ){
    scanf(" %s",&s[0]);
    printf("Case %d: ",CNT++);
    int LEN = strlen(s);
    rep(i,LEN+1) rep(j,LEN+1) memo[i][j] = IINF;
    printf("%d\n",dfs(0,LEN-1));
  }
  return 0;
}