#P4629. [BeiJing2016]打字机
[BeiJing2016]打字机
[BJOI2016] 打字机
题目描述
小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先,需要将一条长度为
的纸带放入打字机。打字机上共有 26 个按键,分别是小写字母 a 到 z 。每当你按下一个按键时,打字机
就会立即在纸带上打印出那个字符,并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技巧,并想尝试新的挑战。
他拿出了一本字典,挑选了 个单词,并给每个单词设定了分数。纸带中每出现一次指定的单词,就会得到对应的分数。按出现的位置分别计分,允许不同出现重叠。例如, 单词 eye 的分数为 , year 的分数为 ,那么纸带 eyeyeyear 的分数为 分。小 J 希望挑战自己,打出分数最高的纸带。
特别地,小 J 偶尔会手抖,按到自己不想输入的字符。由于这台古老的打字机没有退格(删除)功能,所以小 J 只能接受按错这个事实,重新规划在按错的情况下如何得最高分。倘若小 J 有可能在任意位置按错按键,并保证整个过程中按错的次数不超过 次,那么请你算出他在最坏情况下能保证的最高得分。每次先决定要按的键,再得知实际打印的字母。按错时可能打印其他任意一个小写字母。
输入格式
第一行包含 3 个非负整数 ,分别表示单词数量、纸带长度和最多按错次数。
接下来 行,每行为一个字符串 和正整数 ,由空格隔开,描述一个非空小写字母单词及其得分。
输出格式
仅一行,包含一个整数,表示最坏情况下的最大得分。
2 4 1
w 1
ha 9
9
样例解释
以下是一种错误思路:
"共 种情况,即第 位按错、第 位按错、第 位按错和第 位按错。
- 第 位按错(不妨假设按成
x,下同),最高得分为xwha,得分为 。 - 第 位按错,最高得分为
wxha,同样为 分。 - 第 位按错,最高得分为
haxw,同样为 分。 - 第 位按错,最高得分为
hawx,同样为 分。
综上,最坏情况下最高得分为 分。"
这种思路的错误之处在于,你不能根据哪一位按错决定你第一位按哪个键。 换种说法,你在哪一位按错,是在按下那个按键之后才能知道的事情。 正确的思路如下:
- 第 位先按
h,倘若按对, 跳至第 2 步,若按错,跳至第 4 步。 - 第 位按
a,倘若按对, 跳至第 3 步,若按错,跳至第 5 步。 - 第 位和第 位都按
w, 结束。 至多错 1 次,如果剩余两次都按对,得分为 分。如果错一次,得分至少为 分。 - 后面三位依次按
haw, 结束。 因为不会再错, 纸带末尾的haw至少贡献 分。 - 后面两位依次按
ha, 结束。因为不会再错, 纸带末尾的ha至少贡献 分。
综上,最坏情况下,最高得分为 分。
数据范围
,,,,。
| 原赛测试点 | 附加条件 |
|---|---|
| 1–2 | 或 |
| 1–6 | |
| 7–8 | , |
| 9–10 | , |