SRM579 Div1 Easy - UndoHistory

問題

長いから略
与えられるvectorの名前はsとする

解法

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