3610: 编码-训练套题T5T3
Description
3. 编码(compare.pas)
【问题描述】
我们准备根据一份文本编码表对一篇文本进行压缩。编码表的每一项包含两个部分:要编码的字符串和对应的编码。编码是二进制的01串，用来替代文本中相应的字符串以实现压缩编码的目的。这些01串不一定是等长的。文本压缩所要考虑的问题是对给定的文本和编码表，求出能令整个文本的编码最短的二进制串的长度。例如文本:abcdef
编码表
|
字符串 |
a |
abc |
abcd |
bcd |
def |
ef |
|
编码 |
01 |
0 |
1011 |
1 |
10 |
11 |
下面有3种不同的方式进行编码：
方式1：长度为5
|
a |
bcd |
ef |
|
01 |
1 |
11 |
方式2：长度为3
|
abc |
def |
|
0 |
10 |
方式3:长度为6
|
abcd |
ef |
|
1011 |
11 |
很明显，方式2长度最短，你的任务是找出编码后文本的最短长度，若不能进行编码，则输出0.
【输入文件】
输入可能包含多个文本压缩问题。
第一行是一个整数n，表示有n个文本压缩问题。(n<=10)
每个文本压缩问题的描述第一行是要压缩的文本（不超过210个字符），接下来是编码表，每项一行，不超过100项，只包含小写字母，外侧有小括号。
【输出文件】
对应每个文本压缩问题，每行输出一个最小长度
【样例输入】
2
abcdef
(a,01)
(abc,0)
(abcd,1011)
(bcd,1)
(def,10)
(ef,11)
aa
(a,1)
(ab,10)
【样例输出】
3
2
HINT
Dp：
f[i]表示前i个字符编码的最小长度
f[i]=min{f[k]+a[k+1..i]} 其中 a[k+1..i]表示从第K+1 到i的字符编码的长度， a[k+1..i]必须能被一次编码，
故需要预处理出以i结尾的所有编码。