P5839 [USACO19DEC] Moortal Cowmbat G

Bessie has been playing the fighting game "Moortal Cowmbat" for a long time. However, the game developers recently released an update that forces Bessie to change her playstyle. The game uses a total of $M$ keys, labeled as the first $M$ lowercase letters. Bessie's favorite combo in the game is a key string $S$ of length $N$. However, due to the recent update, every combo must be made up of some "combos", where a combo is defined as pressing the same key consecutively at least $K$ times. Bessie wants to modify her favorite combo to create a new combo of the same length $N$, but this new combo must be composed of such key combos to fit the new rules. Bessie needs to spend $a_{ij}$ days to train herself to replace key $i$ with key $j$ at a specific position in the combo (that is, the cost to change a specific character in $S$ from $i$ to $j$ is $a_{ij}$). Note that it may be faster to change key $i$ to some intermediate key $k$ and then change key $k$ to key $j$ than to change directly from key $i$ to key $j$ (or, more generally, there may be a change path from $i$ to $j$ that gives the minimum total cost to finally change $i$ into $j$). Help Bessie find the minimum number of days needed to create a combo that satisfies the new requirements.

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

Output one integer, the minimum number of days needed for Bessie to change her combo into a new combo that satisfies the new requirements.

In this example, the optimal plan is to change `a` to `b`, change `d` to `e`, and then change both `e` characters to `c`. This costs a total of $1+4+0+0=5$ days, and the final combo is `bbccc`. Test point properties: Test points $2\sim 4$ satisfy $N\le 1000$, $K\le 50$. Test points $5\sim 8$ satisfy $N\le 3\times 10^4$, $K\le 50$. For $100\%$ of the data, $1 \leq M \leq 26$, $1 \leq K\leq N \leq 10^5$. Problem by: Eric Wei. Translated by ChatGPT 5