P1279 字串距离 - 洛谷保存站

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

$a:\verb!cmc!$

$b:\verb!snmn!$

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

$A :\verb!?cmc!$

$B :\verb!snmn!$

可以发现此时 $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))$。

正在渲染内容...