Moortal Cowmbat

题目描述:

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

游戏总共使用 M 个按键，标记为前 M 个小写字母（1≤M≤26）。Bessie 在游戏中最喜欢的组合键是一个长为 NN 的按键字符串 S（1≤N≤10⁵）。然而，由于最近的更新，现在每种组合键必须由一些“连击”所组成，其中连击的定义为相同的按键连续按下至少 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 求出她创建一个满足新要求的组合键所需要的最小天数。

测试点性质：

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

输入格式:

输入的第一行包含 N，M 和 K。第二行包含 S，最后 M 行包含一个 M×M 的数字方阵 aij，其中 aij 为一个范围为 0…1000 的整数，并且对于所有的 i，有 aii=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=5天，最终的组合键为 bbccc。

时间限制: 1000ms
空间限制: 256MB

---

来源: USACO 2019 DEC Gold