logo AlgoBeat OnlineJudge
登录 注册

#104674. [BZOJ 4674] 挑选子序列

内存限制:256 MiB 时间限制:15000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

给定3个长度为n的小写字母串s1、s2、t,在串t中挑选出一长度不超过

m的子序列seq,使得该子序列与串s1和串s2的距离的最大值最小,输出该值。

定义串a的位置i与串b的位置j的距离为ASCII差+距离差,即|a[i]-

b[j]|+val[|i-j|],其中val数组给定。

如串a为abc,串b为def。

c和d的距离为|‘c’-‘d’|+val[|3-1|]=1+val[2]

c和e的距离为|‘c’-‘e’|+val[|3-2|]=2+val[1]

c和f的距离为|‘c’-‘f’|+val[|3-3|]=3+val[0]

定义串a的位置i与子序列seq的距离为串a的位置i与子序列seq各位置的距离的最小值。

同样令串a为abc,串b为def。

若取子序列seq为df(即def),

则串a的c与该子序列的距离为min(1+val[2],3+val[0])。

若取子序列seq为ef(即def),

则串a的c与该子序列的距离为min(2+val[1],3+val[0])。

定义串a与子序列seq的距离为串a各位置与子序列seq的距离的最大值。

输入格式

第一行一个整数T表示数据组数。

以下T组数据,每组5行:

第一行两个整数n,m。

第二行n个整数表示val[0]、val[1]……val[n-1]。

第三至第五行每行一长度为n的小写字母串,表示s1,s2,t。

n <= 40, 0 < m <= n, 0 <= val[i] <= 2000, T <= 100

输出格式

T行,格式为“Case#T:Answer”,详见样例

样例

样例输入

2
3 2
0 1 2
azz
zaa
zza
7 2
0 1 2 3 4 5 6
elelele
psypsyp
congroo

样例输出

Case #1: 2
Case #2: 9