SRM579 Div1 Easy - UndoHistory
問題
長いから略
与えられるvector
解法
s[i]をタイプするとき
L = max(s[i]とs[j < i]の最長共通接頭辞の長さ)
とすると、2回のマウスクリックでL文字復元して、残りの |s[i]|-L 文字は手打ちする必要がある
ただs[i]の先頭がs[j]に一致する場合のみ、前のバッファをそのまま使って |s[i]|-|s[j]| 回タイプするって選択肢もある
class UndoHistory { public: int minPresses(vector<string> s) { int n = s.size(), res = 0; rep(i,n) { int l = 0; rep(j,i) { rep(k, min(s[i].size(), s[j].size())) { if (s[i][k]==s[j][k]) chmax(l,k+1); else break; } } if (i==0) res += s[i].size() + 1; else { int t = 2+s[i].size()-l; if (s[i].size()>=s[i-1].size() && s[i].substr(0,s[i-1].size())==s[i-1]) chmin(t, (int)(s[i].size()-s[i-1].size())); res += t+1; } } return res; } };
https://community.topcoder.com/stat?c=problem_statement&pm=12523&rd=15499