A6958. 字符的清理代价
编程题
普及/提高-
知识点
题目描述
给定两个字符串 $S_1$ 和 $S_2$。
你现在需要对它们进行“清理”操作:你可以从任意一个字符串中**删除**任意数量的字符。
目标是让两个字符串在清理后变得**完全相同**。
但是,删除字符是有代价的。每删除一个字符,你就要消耗等于该字符 **ASCII 码值** 的代价。
(例如:删除字符
请问,为了让两个字符串变得相同,你所付出的**最小总代价**是多少?
> 注意:如果最终把两个字符串都删成了空串,它们也被认为是相同的,此时的代价就是原字符串所有字符的 ASCII 码之和。
你现在需要对它们进行“清理”操作:你可以从任意一个字符串中**删除**任意数量的字符。
目标是让两个字符串在清理后变得**完全相同**。
但是,删除字符是有代价的。每删除一个字符,你就要消耗等于该字符 **ASCII 码值** 的代价。
(例如:删除字符
'a' 的代价是 97,删除 'b' 的代价是 98)。请问,为了让两个字符串变得相同,你所付出的**最小总代价**是多少?
> 注意:如果最终把两个字符串都删成了空串,它们也被认为是相同的,此时的代价就是原字符串所有字符的 ASCII 码之和。
输入格式
输入共两行。
第一行包含一个字符串 $S_1$。
第二行包含一个字符串 $S_2$。
第一行包含一个字符串 $S_1$。
第二行包含一个字符串 $S_2$。
输出格式
输出一个整数,表示最小的删除代价总和。
输入输出样例
输入 #1
sea eat
输出 #1
231
输入 #2
delete leet
输出 #2
403
说明/提示
## 样例解释与数据范围
### 样例 #1 解释
- $S_1=$
- 我们希望它们变成相同的字符串
- 操作步骤:
1. 从
2. 从
- 总代价 = $115 + 116 = 231$。
### 样例 #2 解释
- $S_1=$
- 最终目标是将它们都变成
- 需要从
-
- 总代价 = $100 + 101 = 403$。
- (注:如果变成
### 数据范围
- 对于 $100\%$ 的数据,字符串仅包含小写英文字母。
- $1 \le |S_1|, |S_2| \le 500$。
**数据点分布:**
- 测试点 1-5:字符串长度 $\le 10$ (适合手算验证)
- 测试点 6-15:字符串长度 $\le 100$
- 测试点 16-25:字符串长度 $\le 500$
### 样例 #1 解释
- $S_1=$
sea, $S_2=$ eat。- 我们希望它们变成相同的字符串
ea。- 操作步骤:
1. 从
sea 中删除 s (ASCII: 115)。2. 从
eat 中删除 t (ASCII: 116)。- 总代价 = $115 + 116 = 231$。
### 样例 #2 解释
- $S_1=$
delete, $S_2=$ leet。- 最终目标是将它们都变成
leet。- 需要从
delete 中删除 d (100) 和 e (101)。-
leet 不需要删除。- 总代价 = $100 + 101 = 403$。
- (注:如果变成
lee,虽然相等,但代价会更高,因为要多删字符)。### 数据范围
- 对于 $100\%$ 的数据,字符串仅包含小写英文字母。
- $1 \le |S_1|, |S_2| \le 500$。
**数据点分布:**
- 测试点 1-5:字符串长度 $\le 10$ (适合手算验证)
- 测试点 6-15:字符串长度 $\le 100$
- 测试点 16-25:字符串长度 $\le 500$