A - YahooYahooYahoo
編集距離DPをいじった感じでやる。
y f o o
y 0
a
h
o
o
dp[i][j] := yahoo[i]までを、s[j]までで作れる最小手数とする
まず、yahoo[i]までをs[j-1]までで作れる時、jを消せばs[j]までを作れるため
右に+1で遷移できる
また、s[j]において、s[j-1]まででyahooのどの文字までを作れたかの場合についても考えればOK
自分と相手が同じ文字の場合は自分を消せば良く、その他の場合は挿入する文字の数と文字が一致してるかで判断すればいい
簡単のため、頭にyahooをつけた
signed main() {
string s = sin();
s = "yahoo" + s;
N = s.size();
vvi(dp, k5, 5);//si yi
fill(dp, INF);
string ya = "yahoo";
rep(i, 5) {
dp[0][i] = i + (ya[i] == s[0] ? 0 : 1);
}
rep(i, 10) {
chmin(dp[0][i % 5], dp[0][mod(i - 1, 5)] + 1);
}
rep(si, 1, N) {
rep(yi, 5) {
rep(f, 5) {
if (yi == f)continue;
int cost = dp[si - 1][f];
cost += mod(yi - f - 1, 5);
cost += (ya[yi] == s[si] ? 0 : 1);
chmin(dp[si][yi], cost);
}
//文字siを消して、
chmin(dp[si][yi], dp[si - 1][yi] + 1);
rep(i, 10) {
chmin(dp[si][i % 5], dp[si][mod(i - 1, 5)] + 1);
}
}
}
cout << dp[N - 1][4] << endl;
return 0;
}
