SRM411 Div2 Medium

600

memo[ どこまで作った ] = 最小コスト

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

string S;
vector<string> W;

const int inf = 1 << 29;

int cost(string a, string b)
{
  if (a.size() != b.size()) return inf;
  string sa = a;
  string sb = b;
  sort(sa.begin(), sa.end());
  sort(sb.begin(), sb.end());

  if (sa != sb) return inf;

  int diff = 0;
  for (int i = 0; i < b.size(); ++i) {
    diff += a[i] != b[i];
  }
  return diff;
}

int rec(int n)
{
  if (n == S.size()) return 0;
  int &ret = memo[n];
  if (ret != -1) return ret;

  int mn = inf;

  string s;
  for (int i = 0; n + i < S.size(); ++i) {
    s += S[n + i];
    for (int j = 0; j < W.size(); ++j) {
      int m = cost(s, W[j]);
      if (m != inf) {
        mn = min(mn, rec(n + i + 1) + m);
      }
    }
  }

  return ret = mn;
}

class SentenceDecomposition {
public:
  int decompose(string sentence, vector <string> validWords)
  {
    S = sentence;
    W = validWords;

    fill(memo, memo + N, -1);
    int ret = rec(0);
    return ret == inf ? -1 : ret;
  }
};