SRM 579 Div1 250 UndoHistory

2013-05-18

04:35 |

へんなエディタで目的の文字列[]を打つための操作回数の最小値を求める問題。
編集エリアでは, 文字を打つ(1key), 履歴から呼び出す(2click), enter(1key)で内容を行として結果エリアに追記, のどれかができる。
編集エリアに現れた文字列はすべて履歴に追記される
目的の文字列の行数≦50, 各行の文字数≦50

enter後２回目以降に履歴を呼び出すと編集エリアに追記されるのだな（誤読）

提出→再提出→チャレンジされず→failed system test

（あとで）

なんで以前の prefix すべて履歴にあるとしていいのか不思議だったけど編集エリアには履歴から追記できないのでそうなのであった。
最近誤読が多いので落ち着くべき

(accepted in practice room)

class UndoHistory {
	public:
	int minPresses(vector <string> L) {
		int ans = 0;
		REP(i, L.size()) {
			int lans = 1<<30;
			if(i>0 && L[i].find(L[i-1])==0) {
				// 前のをそのまま使う + 残りを打つ
				lans = L[i].size() - L[i-1].size();
			}
			// 必要ならクリアしたあとに全部打つ
			lans = min<int>(lans, (i==0 ? 0 : 2) + L[i].size());
			RANGE(j, 0, i) REP(k, L[j].size()+1) if(L[i].find(L[j].substr(0, k))==0) {
				// 履歴から呼び出したあとに全部打つ
				lans = min<int>(lans, 2 + L[i].size() - k);
			}
			ans += lans + 1;
		}
		return ans;
	}
};