Bessie has been playing the popular fighting game Moortal Cowmbat for a long
time now. However, the game developers have recently rolled out an update that
is forcing Bessie to change her play style.

The game uses \(M\) buttons labeled by the first \(M\) lowercase letters
(\(1 \leq M \leq 26\)). Bessie's favorite combo of moves in the game is a
length-\(N\) string \(S\) of button presses (\(1 \leq N \leq 10^5\)). However, due to
the most recent update, every combo must now be made from a series of "streaks",
where a streak is defined as a series of the same button pressed at least \(K\)
times in a row (\(1 \leq K \leq N\)). Bessie wants to modify her favorite combo to
produce a new combo of the same length \(N\), but made from streaks of button
presses to satisfy the change in rules.

It takes \(a_{ij}\) days for Bessie to train herself to press button \(j\) instead
of button \(i\) at any specific location in her combo (i.e. it costs \(a_{ij}\) to
change a single specific letter in \(S\) from \(i\) to \(j\)). Note that it might
take less time to switch from using button \(i\) to an intermediate button \(k\) and
then from button \(k\) to button \(j\) rather than from \(i\) to \(j\) directly (or
more generally, there may be a path of changes starting with \(i\) and ending with
\(j\) that gives the best overall cost for switching from button \(i\) ultimately to
button \(j\)).

Help Bessie determine the smallest possible number of days she needs to create a
combo that supports the new requirements.

Problem credits: Eric Wei

SCORING

• Test cases 2-4 satisfy \(N\le 1000, K\le 50.\)
• Test cases 5-8 satisfy \(N\le 30,000, K\le 50.\)

Problem credits: Eric Wei

The first line of input contains \(N\), \(M\), and \(K\). The second line contains
\(S\), and the final \(M\) lines contain an \(M\times M\) matrix of values \(a_{ij}\),
where \(a_{ij}\) is an integer in the range \(0 \ldots 1000\) and \(a_{ii} = 0\) for
all \(i\).

Output a single number, representing the minimum number of days Bessie needs to
change her combo into one that satisfies the new requirements.

riseoj 작성

출처 올림피아드 > USACO > 2019-2020 > December > Gold