1443: 小V的匹配作业
题目
题目描述
小V的作业有点简单，他不太想做，所以想请你来帮他做一下。题目是这样的，小V有一个数据库包含 n 个字符串，老师给了一些其他字符串用来询问，有 m 个，想让小V依次找到每个询问的字符串在数据库中“最接近的”字符串。评价两个字符串“最接近”的标准是：将两个字符串”对齐“（对齐的方式为在两个字符串中任意位置插入一些空格，使两个字符串长度相同），然后计算这种“对齐”方式的 cost 。cost 是对两个字符串每一个对应位置的 “分数” 求和，分数计算如下：
- 如果对应位置字符相同，分数为 0；
- 如果对应位置为两个非空格字符，且不相同，分数为 3；
- 如果对应位置有且仅有一个空格，分数为 2。
目标就是找到某种“对齐”方式，使得 cost 最小！对于老师给的每个字符串，你需要在数据库中找出与它最接近的那个字符串。为了减少小V的负担，老师只要求他算出这 m 个字符串中的每个在数据库中匹配之后，最小的 cost。
输入格式
第一行是一个整数 n
接下来 n 行是数据库中的 n 个字符串
下面一行是一个整数 m
接下来是要询问的 m 个字符串
输出格式
输出每个询问的最小 cost ，每行输出一个
样例输入
4
ABBC
ACCA
BBC
ABCD
3
ABCC
ACBC
ACD
样例输出
3
3
2
数据范围
计算举例
ABCD 与 ACD 进行匹配：
ABCD
A-CD
cost = 2
30%的数据：字符串长度不超过 100；0 < n < = 50；0 < m <= 5
100%的数据：字符串长度不超过300; 0 < n < 100; 0 < m < 20
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！