Description

给出两个由小写字母组成的字符串 X 和Y ，我们需要算出两个字符串的距离，定义如下：
1)我们可以在字符串的头、尾、中间插入若干空格，组成一个新的扩展串
2)对X扩展成扩展串X1，对Y扩展成扩展串Y1，并且令X1和Y1具有相同的长度
3)定义X1、Y1的距离为每个对应的字符的距离之和，其中两个空格的距离为0，两个非空格字符的距离为其ASCII码之差的绝对值，一个空格字符到任意非空格字符的距离为K
4)对于字符串X、Y，必然存在两个等长的扩展串X1、Y1，使得X1、Y1的距离达到最少，我们将这一距离定义为字符串X、Y的距离

Input

输入为三行，前两行是30位以内的由小写字母组成的字符串， 第三行是整数K（0<=K<=30）

Output

输出一行为一个整数，代表两个字符串的距离

Sample Input

cmo
snmn
2

Sample Output

7

思路

比赛的时候感觉是个dp，思考了一会儿，于是列出了一个3维的dp（分别记录s1串的位置，s2串的位置，和加了几个空格），但是由于最后一维的限制，我发现了转移方程中的很多锅，最终没能改过来。
本题具体的思路也挺简单：设 $F_{i,j}$ 表示当前在第 $s1$ 串第 $i$ 个位置以及 $s2$ 串第 $j$ 个位置。
那么状态转移方程就是：
$F_{i,j}=min(F_{i-1,j-1}+abs(s{1}_i-s{2}_j),min(F_{i,j-1},F_{i-1,j})+K)$
特别的
$F_{i,0}=F_{0,i}=i\times K$
其实思路很简单，重点其实是在于初始值而已。
以后做dp题的时候打完要多出几个数据检查，不要等到后面才发现问题，不然没时间改了。
并且，遇到此dp状态不好推/很多锅时，要从其他dp状态方面思考，不能只停留在当前的状态。

$Code$

#include<cstdio>
#include<cstring>
using namespace std;
int n1,n2,c,l;
int s1[50],s2[50],f[50][50];
int abs(int x){
	if (x<0) return -x;
	return x;
}
int min(int x,int y){
	return x<y?x:y;
}
int max(int x,int y){
	return x>y?x:y;
}
int main(){
	freopen("distance.in","r",stdin);
	freopen("distance.out","w",stdout);
	char ch=getchar();
	while (ch<'a'||ch>'z') ch=getchar();
	while (ch>='a'&&ch<='z') s1[++n1]=ch-'a',ch=getchar();
	ch=getchar();
	while (ch<'a'||ch>'z') ch=getchar();
	while (ch>='a'&&ch<='z') s2[++n2]=ch-'a',ch=getchar();
	scanf("%d",&l);
	for (int i=1;i<=max(n1,n2);++i) f[i][0]=f[0][i]=i*l;
	for (int i=1;i<=n1;i++){
		for (int j=1;j<=n2;j++){
			f[i][j]=min(f[i-1][j-1]+abs(s1[i]-s2[j]),min(f[i-1][j],f[i][j-1])+l);
		}
	}
	printf("%d",f[n1][n2]);
	fclose(stdin);
	fclose(stdout);
	return 0;
}