A6972. 编辑距离(pro 版本)
编程题
提高+/省选-
知识点
题目描述
有两个字符串 $A, B$，每次可以对 $A$ 进行 $4$ 种操作：
1. 插入一个字符，花费 $t_i$ 元；
2. 删除一个字符，花费 $t_d$ 元；
3. 替换一个字符，花费 $t_r$ 元；
4. 交换相邻的两个字符，花费 $t_e$ 元。
保证费用都是 $[1, 100]$ 之间的正整数，且 $2t_e\geq t_i + t_d$。
求将 $A$ 变成 $B$ 最少需要多少元。
1. 插入一个字符，花费 $t_i$ 元；
2. 删除一个字符，花费 $t_d$ 元；
3. 替换一个字符，花费 $t_r$ 元；
4. 交换相邻的两个字符，花费 $t_e$ 元。
保证费用都是 $[1, 100]$ 之间的正整数，且 $2t_e\geq t_i + t_d$。
求将 $A$ 变成 $B$ 最少需要多少元。
输入格式
第一行四个整数 $t_i, t_d, t_r, t_e$。
接下来两行，每行一个字符串分别表示 $A, B$，保证它们长度都不超过 $4000$。
接下来两行，每行一个字符串分别表示 $A, B$，保证它们长度都不超过 $4000$。
输出格式
一行一个整数表示最小费用。
输入输出样例
输入 #1
1 1 1 1 youshouldnot thoushaltnot
输出 #1
5
输入 #2
2 4 10 3 ab ba
输出 #2
3
输入 #3
1 10 20 30 a za
输出 #3
1