[USACO19DEC] Moortal Cowmbat G
题目描述
Bessie 玩格斗游戏真牛快打已经有很长时间了。然而,最近游戏开发者发布了一项更新,这迫使 Bessie 改变她的打法。
游戏总共使用 $M$ 个按键,标记为前 $M$ 个小写字母。Bessie 在游戏中最喜欢的组合键是一个长为 $N$ 的按键字符串 $S$。然而,由于最近的更新,现在每种组合键必须由一些“连击”所组成,其中连击的定义为相同的按键连续按下至少 $K$ 次。Bessie想要修改她最喜欢的组合键,创造一个同样长为 $N$ 的新组合键,然而这一新组合键由按键连击所组成,以适应规则的变化。
Bessie 需要消耗 $a_{ij}$ 天来训练她在组合键中某个特定的位置用按键 $j$ 来取代按键 $i$(也就是说,将 $S$ 中的某个特定的字符由 $i$ 变为 $j$ 的代价为 $a_{ij}$)。注意有可能将按键 $i$ 换成某种中间按键 $k$ 然后再从按键 $k$ 换成按键 $j$ 会比直接从按键 $i$ 换成按键 $j$ 消耗更短的时间(或者更一般地说,可能有一条起点为 $i$ 终点为 $j$ 的更改路径给出了从按键 $i$ 最终更改为按键 $j$ 的最小总代价)。
帮助 Bessie 求出她创建一个满足新要求的组合键所需要的最小天数。
输入输出格式
输入格式
输入的第一行包含 $N$,$M$ 和 $K$。第二行包含 $S$,最后 $M$ 行包含一个 $M\times M$ 的数字方阵 $a_{ij}$,其中 $a_{ij}$ 为一个范围为 $0 \ldots 1000$ 的整数,并且对于所有的 $i$,有 $a_{ii} = 0$。
输出格式
输出一个整数,表示 Bessie 将她的组合键改为一个满足新要求的新的组合键所需要的最小天数。
输入输出样例
输入样例 #1
5 5 2
abcde
0 1 4 4 4
2 0 4 4 4
6 5 0 3 2
5 5 5 0 4
3 7 0 5 0
输出样例 #1
5
说明
在这个例子中的最优方案是将 `a` 改为 `b`,将 `d` 改为 `e`,再将两个 `e` 都改为 `c`。这总共消耗 $1+4+0+0=5$ 天,最终的组合键为 `bbccc`。
测试点性质:
测试点 $2\sim 4$ 满足 $N\le 1000$,$K\le 50$。
测试点 $5\sim 8$ 满足 $N\le 3\times 10^4$,$K\le 50$。
对于 $100\%$ 的数据,$1 \leq M \leq 26$,$1 \leq K\leq N \leq 10^5$。
供题:Eric Wei