#P4629. [BeiJing2016]打字机

[BeiJing2016]打字机

[BJOI2016] 打字机

题目描述

小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先,需要将一条长度为 mm 的纸带放入打字机。打字机上共有 26 个按键,分别是小写字母 a 到 z 。每当你按下一个按键时,打字机 就会立即在纸带上打印出那个字符,并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技巧,并想尝试新的挑战。

他拿出了一本字典,挑选了 nn 个单词,并给每个单词设定了分数。纸带中每出现一次指定的单词,就会得到对应的分数。按出现的位置分别计分,允许不同出现重叠。例如, 单词 eye 的分数为 22, year 的分数为 33,那么纸带 eyeyeyear 的分数为 99 分。小 J 希望挑战自己,打出分数最高的纸带。

特别地,小 J 偶尔会手抖,按到自己不想输入的字符。由于这台古老的打字机没有退格(删除)功能,所以小 J 只能接受按错这个事实,重新规划在按错的情况下如何得最高分。倘若小 J 有可能在任意位置按错按键,并保证整个过程中按错的次数不超过 kk 次,那么请你算出他在最坏情况下能保证的最高得分。每次先决定要按的键,再得知实际打印的字母。按错时可能打印其他任意一个小写字母。

输入格式

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

接下来 nn 行,每行为一个字符串 SS 和正整数 aia_i,由空格隔开,描述一个非空小写字母单词及其得分。

输出格式

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

2 4 1
w 1
ha 9
9

样例解释

以下是一种错误思路:

"共 44 种情况,即第 11 位按错、第 22 位按错、第 33 位按错和第 44 位按错。

  1. 第 11 位按错(不妨假设按成 x,下同),最高得分为 xwha,得分为 1010。
  2. 第 22 位按错,最高得分为 wxha,同样为 1010 分。
  3. 第 33 位按错,最高得分为 haxw,同样为 1010 分。
  4. 第 44 位按错,最高得分为 hawx,同样为 1010 分。

综上,最坏情况下最高得分为 1010 分。"

这种思路的错误之处在于,你不能根据哪一位按错决定你第一位按哪个键。 换种说法,你在哪一位按错,是在按下那个按键之后才能知道的事情。 正确的思路如下:

  1. 第 11 位先按 h,倘若按对, 跳至第 2 步,若按错,跳至第 4 步。
  2. 第 22 位按 a,倘若按对, 跳至第 3 步,若按错,跳至第 5 步。
  3. 第 33 位和第 44 位都按 w, 结束。 至多错 1 次,如果剩余两次都按对,得分为 1111 分。如果错一次,得分至少为 1010 分。
  4. 后面三位依次按 haw, 结束。 因为不会再错, 纸带末尾的 haw 至少贡献 1010 分。
  5. 后面两位依次按 ha, 结束。因为不会再错, 纸带末尾的 ha 至少贡献 99 分。

综上,最坏情况下,最高得分为 99 分。

数据范围

0≤n≤1000\le n\le100,0≤m≤1090\le m\le10^9,0≤k≤50\le k\le5,∑i∣Si∣≤500\sum_i \lvert S_i\rvert\le500,1≤ai≤10001\le a_i\le1000。

原赛测试点 附加条件
1–2 n=1n=1 或 k=0k=0
1–6 m≤500m\le500
7–8 k=0k=0,∑i∣Si∣≤200\sum_i \lvert S_i\rvert\le200
9–10 ∑i∣Si∣≤50\sum_i \lvert S_i\rvert\le50,ai≤1a_i\le1