SRM437 Div2 Medium

500

メモ化する。
貪欲だと思って撃沈した。

const int N = 11;
map<string, string> memo[N];

string rec(string s, int k)
{
  if (k == 0) return s;
  if (memo[k].count(s)) return memo[k][s];
  string mx = "0";
  for (int i = 0; i < s.size(); ++i) {
    for (int j = i + 1; j < s.size(); ++j) {
      if (i == 0 && s[j] == '0') continue;
      swap(s[i], s[j]);
      mx = max(mx, rec(s, k - 1));
      swap(s[i], s[j]);
    }
  }
  return memo[k][s] = mx;
}

class TheSwap {
public:
  int findMax(int n, int k)
  {
    char buff[100];
    sprintf(buff, "%d", n);
    string s(buff);

    bool valid = false;
    for (int i = 0; i < s.size(); ++i) {
      for (int j = i + 1; j < s.size(); ++j) {
        int a = s[i] - '0';
        int b = s[j] - '0';
        if (a && b) valid = true;
        if (a == b) valid = true;
      }
    }
    if (!valid) return -1;

    fill(memo, memo + N, map<string, string>());
    return atoi(rec(s, k).c_str());
  }
};