Moortal Cowmbat

题目描述

Bessie 已经玩热门格斗游戏 Moortal Cowmbat 很久了。然而，游戏开发者最近推出了一次更新，迫使 Bessie 改变她的游戏风格。 游戏使用 $M$ 个按钮，分别用前 $M$ 个小写字母标记（$1 \leq M \leq 26$）。Bessie 最喜欢的连招是在游戏中一段长度为 $N$ 的按钮按压字符串 $S$（$1 \leq N \leq 10^5$）。然而，由于最新的更新，现在每个连招都必须由一系列“连段（streaks）”组成，其中连段被定义为：同一个按钮连续按下至少 $K$ 次（$1 \leq K \leq N$）。Bessie 想修改她最喜欢的连招，生成一个长度仍为 $N$ 的新连招，但必须由按钮连段构成以满足规则变化。 在连招的任意具体位置上，将按钮 $i$ 改为按钮 $j$ 需要 $a_{ij}$ 天训练时间（即把 $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 将她的连招改成满足新要求的连招所需的最少天数。

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

提示

SCORING: 测试点 2-4 满足 $N\le 1000, K\le 50.$ 测试点 5-8 满足 $N\le 30,000, K\le 50.$

本例中的最优解是将 a 变为 b，将 d 变为 e，然后将两个 e 都变为 c。这样总共需要 $1+4+0+0=5$ 天，最终连招字符串为 bbccc。

题目来源：Eric Wei

标签: USACO|2019|Gold

来源

USACO|2019|Gold