3321. [USACO19 DEC Gold]Moortal Cowmbat

【题目描述】

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

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

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

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

【输入格式】

输入的第一行包含N，M 和K。第二行包含S，最后M 行包含一个;M×M 的数字方阵aij，其中aij 为一个范围为0…1000 的整数，并且对于所有的i，有aij=0。

【输出格式】

【样例输入】

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=5天，最终的组合键为 bbccc。

测试点性质：

测试点 2-4 满足N≤1000,K≤50。

测试点 5-8 满足N≤30,000,K≤50。

【来源】

在此键入。