#P5839. [USACO19DEC] Moortal Cowmbat G
[USACO19DEC] Moortal Cowmbat G
题目描述
Bessie 玩格斗游戏真牛快打已经有很长时间了。然而,最近游戏开发者发布了一项更新,这迫使 Bessie 改变她的打法。
游戏总共使用 个按键,标记为前 个小写字母。Bessie 在游戏中最喜欢的组合键是一个长为 的按键字符串 。然而,由于最近的更新,现在每种组合键必须由一些“连击”所组成,其中连击的定义为相同的按键连续按下至少 次。Bessie想要修改她最喜欢的组合键,创造一个同样长为 的新组合键,然而这一新组合键由按键连击所组成,以适应规则的变化。
Bessie 需要消耗 天来训练她在组合键中某个特定的位置用按键 来取代按键 (也就是说,将 中的某个特定的字符由 变为 的代价为 )。注意有可能将按键 换成某种中间按键 然后再从按键 换成按键 会比直接从按键 换成按键 消耗更短的时间(或者更一般地说,可能有一条起点为 终点为 的更改路径给出了从按键 最终更改为按键 的最小总代价)。
帮助 Bessie 求出她创建一个满足新要求的组合键所需要的最小天数。
输入格式
输入的第一行包含 , 和 。第二行包含 ,最后 行包含一个 的数字方阵 ,其中 为一个范围为 的整数,并且对于所有的 ,有 。
输出格式
输出一个整数,表示 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
。这总共消耗 天,最终的组合键为 bbccc
。
测试点性质:
测试点 满足 ,。
测试点 满足 ,。
对于 的数据,,。
供题:Eric Wei