UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4629. [BeiJing2016]打字机

统计 下载数据

Description

小 J 在搬家的过程中发现了一台古老的打字机。 好奇的小 J 决定研究如何使用它。首先,需要将一条长度为 m 
的纸带放入打字机。打字机上共有 26 个按键,分别是小写字母 ’a’ - ’z’。每当你按下一个按键时,打字机
就会立即在纸带上打印出那个字符,并将纸带平移一个单位距离。聪明的小 J 很快就掌握了这款打字机的使用技
巧,并想尝试新的挑战。他拿出了一本字典,挑选了 n 个单词,并给每个单词设定了分数。纸带中每出现一次指
定的单词,就会得到对应的分数。例如, 单词 ’eye’ 的分数为 2, ’year’ 的分数为 3,那么纸带 ’eyeye
year’ 的分数为 9 分。小 J 希望挑战自己,打出分数最高的纸带。特别地,小 J 偶尔会手抖,按到自己不想输
入的字符。由于这台古老的打字机没有退格(删除)功能,所以小 J 只能接受按错这个事实,重新规划在按错的
情况下如何得最高分。倘若小 J 有可能在任意位置按错按键,并保证整个过程中按错的次数不超过 k 次,那么请
你算出他在最坏情况下的最高得分是多少。

Input

第一行包含 3 个非负整数 n, m, k,分别表示单词数量、纸带长度和最多按错次数。
接下来 n 行,每行为一个字符串 Si和正整数 Ai,由空格隔开,描述一个单词及其得分。
n ≤ 100, m ≤ 109,∑|Si| ≤ 500, Ai ≤1000, k ≤ 5

Output

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

Sample Input

2 4 1
w 1
ha 9

Sample Output

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 分

Hint

测试点 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比较大的那些测试点是有特殊性质的

Source