問題
http://community.topcoder.com/stat?c=problem_statement&pm=12523&rd=15499
解き方
前の文字列からそのまま続けられる時はその場合と、
以前の部分文字列を使う場合のうち最小のものを採用していけばよい。
コード
class UndoHistory {
public: int minPresses(vector<string> lines) {
int n=lines.size();
int ret=n;
string prev="";
FORE(i,0,n){
int cost=1e+9;
if(prev.size()<=lines[i].size()){
int valid=1;
FORE(j,0,prev.size())if(prev[j]!=lines[i][j])valid=0;
if(valid)cost=min(cost,(int)lines[i].size()-(int)prev.size());
}
FORE(j,0,i){
int tmp=0;
for(int k=0;k<lines[i].size() && k<lines[j].size();k++){
if(lines[i][k]==lines[j][k])tmp++;
else break;
}
cost=min(cost,(int)lines[i].size()-tmp+2);
}
ret+=cost;
prev=lines[i];
}
return ret;
}
};
public: int minPresses(vector<string> lines) {
int n=lines.size();
int ret=n;
string prev="";
FORE(i,0,n){
int cost=1e+9;
if(prev.size()<=lines[i].size()){
int valid=1;
FORE(j,0,prev.size())if(prev[j]!=lines[i][j])valid=0;
if(valid)cost=min(cost,(int)lines[i].size()-(int)prev.size());
}
FORE(j,0,i){
int tmp=0;
for(int k=0;k<lines[i].size() && k<lines[j].size();k++){
if(lines[i][k]==lines[j][k])tmp++;
else break;
}
cost=min(cost,(int)lines[i].size()-tmp+2);
}
ret+=cost;
prev=lines[i];
}
return ret;
}
};