SRM579 Div1 Easy

250

最初の行は全てタイプするしかない。
それ以外は、
1.直前のバッファにそのまま付け足す。
2.履歴からプレフィックスに一致する文をもってくる。
3.バッファを消して全てタイプする。

string pref(string a, string b)
{
  string c;
  for (int i = 0; i < min(a.size(), b.size()); ++i) {
    if (a[i] == b[i]) c += a[i];
    else break;
  }
  return c;
}

class UndoHistory {
public:
  int minPresses(vector <string> ls)
  {
    int ret = 0;

    const int click = 2;
    const int enter = 1;

    for (int i = 0; i < ls.size(); ++i) {
      int mn = ls[i].size();
      if (i) {
        if (ls[i - 1].size() == pref(ls[i], ls[i - 1]).size()) {
          int diff = ls[i].size() - ls[i - 1].size();
          mn = min(mn, diff);
        } else {
          mn += click;
        }
      }
      for (int j = 0; j < i; ++j) {
        string comm =  pref(ls[i], ls[j]);
        int m = click + (ls[i].size() - comm.size());
        mn = min(mn, m);
      }
      ret += mn + enter;
    }

    return ret;
  }


};