SRM439 Div2 1000

問題

ある文字列が与えられる．それが回文になるためには「1文字挿入する」「1文字消す」「1文字を他の文字と変える」「2つの文字を交換する」の操作を最低何回行わなければならないか．

考え方

編集距離(レーベンシュタイン距離)．
文字列aと文字列bの文字を「1文字削除」「1文字追加」「1文字置換」をコスト1で可能なとき，同じ文字列にするするまでにかかる最小コストを求める．

この問題では，コストは回数になる．
回文に適用するためには，「元の文字列」と「元の文字列を反転させた文字列」の編集距離を求めて，(対称なので2回操作してしまうから)2で割ると求められる．

swapは1回のみできるので，「1回もしない場合の編集距離」と「1回した場合の編集距離」をそれぞれ考える．もしswapした時は，swap分1回足す．