P1279 字串距离

CQ_Alice · 2023-10-05 16:53:43 · 个人记录

对于给定两个字符串 a 和 b，得到 a,b 的扩展串为 A,B（扩展串即题目中的定义），那么我们很容易想到若 A,B 的第 i 个位置上有空格，则意味着这一位置上的字符将作废，从而变成添加空格的费用。

扩展后可以得到 （? 表示空格）

可以发现此时 B 的第一个字符虽然是一个非空格字符，但是由于这一位置在 A 中为空格字符，所以这一位产生的距离也就与字符本身没有关系了，这等价于我们花费了 K 的距离（K 为题目中所述），在接下来不再需要考虑 b 的第一位所产生的距离，即删除了 b 的这一位。

所以我们可以将问题转化，如下：

给定两个字符串，你可以在这两个字符串分别删除掉若干个字符。每删除一个字符将花费 K 的距离代价，使得删除字符后的两个字符串长度相等，且距离代价最小（这里的距离代价指删除花费的距离代价和删完后每一位的距离代价）。

如果这样的话那么这道题就很好想了，考虑动态规划解决这一类问题。

设计 dp 状态 f_{i,j} 表示 a 的前 i 位和 b 的前 j 位通过删除一些字符使得长度一致时能够达到的最小距离代价（注意这里的字符串 a,b 指没有进行扩展的原输入字符串）

那么接下来考虑转移，对于 a 的前 i 位和 b 的前 j 位，则有三种转移方式：

1. 删除 a 的第 i 位（需要 K 的距离代价），不再考虑 a 的第 i 位的任何影响，则等价于 a 的前 i-1 位和 b 的前 j 位匹配（匹配指通过删除字符得到一致的长度）的最小距离代价。

得到该情况的转移式子：f_{i,j}=min(f_{i-1,j}+K)

2. 删除 b 的第 j 位（需要 K 的距离代价），不再考虑 b 的第 j 位的任何影响，则等价于 b 的前 j-1 位和 a 的前 i 位匹配（匹配指通过删除字符得到一致的长度）的最小距离代价。

得到该情况的转移式子：f_{i,j}=min(f_{i,j-1}+K)

3. 我们希望 a 的第 i 位和 b 的第 j 位都不要删除掉，则此时由于状态定义保证 i 和 j 应该为同一位（状态保证两字符串长度一致，且此时 i 和 j 都为未删除的最后一位置 ），那么此时处于同一位置的都未删除的两个字符应考虑距离代价，根据题目对非空字符距离的定义，得到此时的距离代价为 abs(a_i-b_i)（a_i-b_i 在编译器里会自动转换成为字符ASCII码的计算），由于 a 的第 i位和 b 的第 j 位都考虑好了，那么得到转移式子：f_{i,j}=min(f_{i-1,j-1}+abs(a_i-b_i))。