P5164: 编码-训练套题T5T3
传统题
1.000s
时间限制
128MB
内存限制
3 提交
3 解决
【题目描述】
3. 编码(compare.pas)
【问题描述】
我们准备根据一份文本编码表对一篇文本进行压缩。编码表的每一项包含两个部分
:要编码的字符串和对应的编码。编码是二进制的
01串，用来替代文本中相应的字符串以实现压缩编码的目的。这些
01串不一定是等长的。文本压缩所要考虑的问题是对给定的文本和编码表，求出能令整个文本的编码最短的二进制串的长度。例如文本
:abcdef
编码表
|
字符串
|
a
|
abc
|
abcd
|
bcd
|
def
|
ef
|
|
编码
|
01
|
0
|
1011
|
1
|
10
|
11
|
下面有
3种不同的方式进行编码：
方式
1：长度为
5
方式
2：长度为
3
方式
3:长度为
6
很明显，方式
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
【提示】
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结尾的所有编码。