#104629. [BZOJ 4629] [BeiJing2016]打字机

小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先，需要将一条长度为 m

的纸带放入打字机。打字机上共有 26 个按键，分别是小写字母 ’a’ - ’z’。每当你按下一个按键时，打字机

就会立即在纸带上打印出那个字符，并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技

巧，并想尝试新的挑战。他拿出了一本字典，挑选了 n 个单词，并给每个单词设定了分数。纸带中每出现一次指

定的单词，就会得到对应的分数。例如， 单词 ’eye’ 的分数为 2， ’year’ 的分数为 3，那么纸带 ’eyeye

year’ 的分数为 9 分。小 J 希望挑战自己，打出分数最高的纸带。特别地，小 J 偶尔会手抖，按到自己不想输

入的字符。由于这台古老的打字机没有退格（删除）功能，所以小 J 只能接受按错这个事实，重新规划在按错的

情况下如何得最高分。倘若小 J 有可能在任意位置按错按键，并保证整个过程中按错的次数不超过 k 次，那么请

你算出他在最坏情况下的最高得分是多少。

第一行包含 3 个非负整数 n, m, k，分别表示单词数量、纸带长度和最多按错次数。

接下来 n 行，每行为一个字符串 Si和正整数 Ai，由空格隔开，描述一个单词及其得分。

n ≤ 100， m ≤ 109，∑|Si| ≤ 500， Ai ≤1000， k ≤ 5

仅一行，包含一个整数，表示最坏情况下的最大得分

样例输入

2 4 1
w 1
ha 9

样例输出

9
//首先，展示一种错误的思路如下：
“共 4 种情况，即第 1 位按错、第 2 位按错、第 3 位按错和第 4 位按错。
1、第 1 位按错（不妨假设按成 ’x’，下同），最高得分为 ’xwha’，得分为 10。
2、第 2 位按错，最高得分为 ’wxha’，同样为 10 分。
3、第 3 位按错，最高得分为 ’haxw’，同样为 10 分。
4、第 4 位按错，最高得分为 ’hawx’，同样为 10 分。
综上，最坏情况下最高得分为 10 分。”
这种思路的错误之处在于，你不能根据哪一位按错决定你第一位按哪个键。 换种说法，
你在哪一位按错，是在按下那个按键之后才能知道的事情。 正确的思路如下：
1、第 1 位先按 ’h’，倘若按对， goto 2，倘若按错， goto 4；
2、 第 2 位按 ’a’，倘若按对， goto 3，倘若按错， goto 5；
3、 第 3 位和第 4 位都按 ’w’， 结束。 至多错 1 次，最终纸带为 ’hawx’ 或 ’haxw’，
得分为 10 分。
4、后面三位依次按 ’haw’， 结束。 因为不会再错， 最终纸带为’xhaw’，得分为 10 分。
5、后面两位依次按 ’ha’， 结束。因为不会再错， 最终纸带为’hxha’，得分为 9 分。
综上，最坏情况下，最高得分为 9 分

测试点 1 – 2 满足，n = 1 或 k = 0；

测试点 1 – 6 满足，n ≤ 100，m ≤ 500，∑|Si| ≤ 500，A i ≤1000；

测试点 7 – 8 满足，k = 0，∑|Si| ≤ 200；

测试点 9 – 10 满足，∑|Si| ≤ 50，A i ≤1。

对于 100%的数据，n ≤ 100，m ≤ 10 9 ，∑|Si| ≤ 500，A i ≤1000，k ≤ 5。

也就是说对于m比较大的那些测试点是有特殊性质的