Luogu

分析

这是一道DP题。
设$f[i][j]$表示A串的前i个字符和B串的前j个字符的最小字串距离。

A串的第i个字符可以与B串的第j个字符匹配，也可以和空格匹配，B串的第j个字符也可以和空格匹配。
那么我们得到状态转移方程：
$f[i] [j] = min(min(f[i] [j-1],f[i-1] [j])+k, f[i-1] [j-1]+|a[i]-b[i]|)$

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
char a[2010],b[2010];
int f[2010][2010];
int main()
{
    int k; gets(a); gets(b); scanf("%d",&k); //输入  
    int la=strlen(a),lb=strlen(b); f[0][0]=0;
    for (int i=1;i<=la;i++) f[i][0]=i*k; //全是空格的情况  
    for (int i=1;i<=lb;i++) f[0][i]=i*k; //同上  
    for (int i=1;i<=la;i++) //DP过程（核心代码） 
        for (int j=1;j<=lb;j++)
        {
            int now=abs(a[i-1]-b[j-1]); 
            f[i][j]=min(min(f[i-1][j],f[i][j-1])+k,f[i-1][j-1]+now);
        }
    printf("%d\n",f[la][lb]); //输出答案  
    return 0;
}

提示

• 注意到输入为字符串，所以下标要注意
• 要分三种情况，不要遗漏
• 注意边界