SRM579 Div1 Easy

250

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

view plainprint?

1. string pref(string a, string b)  
2. {  
3.   string c;  
4.   for (int i = 0; i < min(a.size(), b.size()); ++i) {  
5.     if (a[i] == b[i]) c += a[i];  
6.     else break;  
7.   }  
8.   return c;  
9. }  
10.   
11. class UndoHistory {  
12. public:  
13.   int minPresses(vector <string> ls)  
14.   {  
15.     int ret = 0;  
16.   
17.     const int click = 2;  
18.     const int enter = 1;  
19.   
20.     for (int i = 0; i < ls.size(); ++i) {  
21.       int mn = ls[i].size();  
22.       if (i) {  
23.         if (ls[i - 1].size() == pref(ls[i], ls[i - 1]).size()) {  
24.           int diff = ls[i].size() - ls[i - 1].size();  
25.           mn = min(mn, diff);  
26.         } else {  
27.           mn += click;  
28.         }  
29.       }  
30.       for (int j = 0; j < i; ++j) {  
31.         string comm =  pref(ls[i], ls[j]);  
32.         int m = click + (ls[i].size() - comm.size());  
33.         mn = min(mn, m);  
34.       }  
35.       ret += mn + enter;  
36.     }  
37.   
38.     return ret;  
39.   }  
40.   
41.   
42. };  

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;
  }


};