4674. 挑选子序列
#4674. 挑选子序列
题目描述
给定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