SRM439 Div2 Hard

1000

dpするだけ。

const int N = 50 + 1;
int memo[N][N];

string S;

int rec(int i, int j)
{
  int &ret = memo[i][j];
  if (ret != -1) return ret;
  if (j <= i) return ret = 0;

  int mn = 1 << 30;

  mn = min(mn, rec(i + 1, j) + 1);
  mn = min(mn, rec(i, j - 1) + 1);
  mn = min(mn, rec(i + 1, j - 1) + (S[i] != S[j]));

  return ret = mn;
}

class PalindromeFactory {
public:
  int getEditDistance(string ini)
  {
    S = ini;
    const int size = S.size();

    fill(&memo[0][0], &memo[N][0], -1);
    int mn = rec(0, size - 1);

    for (int i = 0; i < size; ++i) {
      for (int j = i + 1; j < size; ++j) {
        fill(&memo[0][0], &memo[N][0], -1);
        swap(S[i], S[j]);
        mn = min(mn, rec(0, size - 1) + 1);
        swap(S[i], S[j]);
      }
    }
    return mn;
  }
};