問題文
個の文字列 が与えられます。
わりとねこくんは、これらすべての文字列を元の文字列 のうちのいずれか つと完全に一致させたいと考えています。
最初、わりとねこくんはいずれの文字列の編集画面も開いていません。
わりとねこくんはコストを支払うことで、以下の 種類の操作を好きな順序で好きな回数行うことができます。
- 画面の移動: コスト を支払う。任意の文字列 () を つ選び、その文字列の編集画面に移動する。
- 文字の編集: コスト を支払う。現在開いている文字列に対して、以下のいずれかの操作を 回行う。
- 好きな位置に英小文字を 文字挿入する。
- 好きな位置の文字を 文字削除する。
- 好きな位置の文字を別の英小文字に変更する。
適切な操作を行い、すべての文字列を元の 個の文字列のいずれか つと同じ文字列にするために必要な合計コストの最小値を求めてください。
制約
- は英小文字のみからなる長さ 以上の文字列
- は整数
入力
入力は以下の形式で標準入力から与えられます。
出力
必要な合計コストの最小値を 行に出力してください。
入力例 1
4 2 3
cat
cats
cut
at
出力例 1
15
すべての文字列を と同じ cat に揃えることを考えます。
- の編集画面に移動します。
- の 文字目の
sを削除します。catsはcatになります。 - の編集画面に移動します。
- の 文字目の
uをaに変更します。cutはcatになります。 - の編集画面に移動します。
- の先頭に
cを挿入します。atはcatになります。
画面の移動と文字の編集をそれぞれ 回行ったので、合計コストは です。 元の 個の文字列はすべて異なるため、どれに揃える場合も少なくとも 個の文字列を編集する必要があります。したがって、 が最小です。
入力例 2
3 9 8
neko
neko
neko
出力例 2
0
最初からすべての文字列が一致しているので、操作は不要です。
入力例 3
6 3 1
aaaa
aaaa
aaab
aabb
abbb
bbbb
出力例 3
22
参加受付は終了しました。
ログインして解答を提出
解答の提出や採点結果の確認には、ログインが必要です。
ログインする