每天一题：洛谷P1279 字串距离
目录
题目描述
输入格式
输出格式
输入输出样例
输入 #1
输出 #1
题目详解
解题思路
代码
题目描述
设有字符串 X，我们称在 X 的头尾及中间插入任意多个空格后构成的新字符串为 X 的扩展串，如字符串 X 为abcbcd，则字符串 abcb␣cd，␣a␣bcbcd␣ 和 abcb␣cd␣ 都是 X 的扩展串，这里 ␣ 代表空格字符。
如果 A1 是字符串 A 的扩展串，B1 是字符串 B 的扩展串，A1 与 B1 具有相同的长度，那么我们定义字符串 A1 与 B1 的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的 ASCII 码的差的绝对值，而空格字符与其他任意字符之间的距离为已知的定值K，空格字符与空格字符的距离为 0。在字符串 A、B 的所有扩展串中，必定存在两个等长的扩展串 A1，B1，使得 A1 与 B1 之间的距离达到最小，我们将这一距离定义为字符串 A，B 的距离。
请你写一个程序，求出字符串 A，B 的距离。
输入格式
输入文件第一行为字符串 A ，第二行为字符串 B。A，B 均由小写字母组成且长度均不超过 2000。第三行为一个整数 K(1≤K≤100)，表示空格与其他字符的距离。
输出格式
输出文件仅一行包含一个整数，表示所求得字符串 A,B 的距离。
输入输出样例
输入 #1
cmc snmn 2
输出 #1
10
题目详解
有两个字符串，求距离
若字符串a1是由a在任意地方加空格而来的，那么a1是a的扩展串
字符串a和b的距离是指a的拓展串与b的相同长度的拓展串的最小距离，若两个拓展串的第i个位置都为字母，则距离是字母的差的绝对值，若其中一个是空格，则距离为k，如两个都是空格，则距离为0.
解题思路
这是一道dp题
我们设dp[i][j]为字符串a前i个位置与字符串b前j个位置的最小距离。
对于dp[i][j]，有三种状态：
- 串a的第i个字符和串b的第j个字符都是字母
- 串a的第i个字符换成空格
- 串b的第j个字符换成空格
- 对于都是空格的情况，由于距离是零，讨论此状态没有意义
所以状态转移方程就出来了。
代码
先说一下，别抄袭，这是不好的（其实我早知道一些小盆友想看这个了）
#include<bits/stdc++.h>//一个很妙的开头
#define N 10001//一个预处理
using namespace std;
int dp[N][N],k;//dp[i][j]表示a前i个字符和b前j个字符的最小距离
char a[N],b[N];
int main(){scanf("%s%s%d",&a,&b,&k);int lena=strlen(a),lenb=strlen(b);for(int i=1;i<=lena;i++){dp[i][0]=i*k;//初始化为字符对应空格的形式 }for(int i=1;i<=lenb;i++){dp[0][i]=i*k;}for(int i=1;i<=lena;i++){for(int j=1;j<=lenb;j++){int cha=abs(a[i-1]-b[j-1]);//计算差的绝对值，因为字符串从一开始，所以要-1 dp[i][j]=min(dp[i-1][j-1]+cha,min(dp[i-1][j],dp[i][j-1])+k);//看上文就知道了 }}printf("%d",dp[lena][lenb]);//输出 return 0;//完美收场
}