#P5839. [USACO19DEC] Moortal Cowmbat G

[USACO19DEC] Moortal Cowmbat G

题目描述

Bessie 玩格斗游戏真牛快打已经有很长时间了。然而,最近游戏开发者发布了一项更新,这迫使 Bessie 改变她的打法。

游戏总共使用 MM 个按键,标记为前 MM 个小写字母。Bessie 在游戏中最喜欢的组合键是一个长为 NN 的按键字符串 SS。然而,由于最近的更新,现在每种组合键必须由一些“连击”所组成,其中连击的定义为相同的按键连续按下至少 KK 次。Bessie想要修改她最喜欢的组合键,创造一个同样长为 NN 的新组合键,然而这一新组合键由按键连击所组成,以适应规则的变化。

Bessie 需要消耗 aija_{ij} 天来训练她在组合键中某个特定的位置用按键 jj 来取代按键 ii(也就是说,将 SS 中的某个特定的字符由 ii 变为 jj 的代价为 aija_{ij})。注意有可能将按键 ii 换成某种中间按键 kk 然后再从按键 kk 换成按键 jj 会比直接从按键 ii 换成按键 jj 消耗更短的时间(或者更一般地说,可能有一条起点为 ii 终点为 jj 的更改路径给出了从按键 ii 最终更改为按键 jj 的最小总代价)。

帮助 Bessie 求出她创建一个满足新要求的组合键所需要的最小天数。

输入格式

输入的第一行包含 NNMMKK。第二行包含 SS,最后 MM 行包含一个 M×MM\times M 的数字方阵 aija_{ij},其中 aija_{ij} 为一个范围为 010000 \ldots 1000 的整数,并且对于所有的 ii,有 aii=0a_{ii} = 0

输出格式

输出一个整数,表示 Bessie 将她的组合键改为一个满足新要求的新的组合键所需要的最小天数。

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
5

提示

在这个例子中的最优方案是将 a 改为 b,将 d 改为 e,再将两个 e 都改为 c。这总共消耗 1+4+0+0=51+4+0+0=5 天,最终的组合键为 bbccc

测试点性质:

测试点 242\sim 4 满足 N1000N\le 1000K50K\le 50

测试点 585\sim 8 满足 N3×104N\le 3\times 10^4K50K\le 50

对于 100%100\% 的数据,1M261 \leq M \leq 261KN1051 \leq K\leq N \leq 10^5

供题:Eric Wei