记录编号	30788	评测结果	AAAAAAAAAA
题目名称	字符串的距离	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.178 s
提交时间	2011-10-31 13:14:53	内存使用	15.69 MiB

#include <cstdio>
#include <cstring>
using namespace std;

int f[2011][2011]={{0}};

int absint(int a)
{
	if (a<0)
		a=-a;
	return(a);
}

int main(void)
{
	freopen("blast.in","r",stdin);
	freopen("blast.out","w",stdout);
	int i,j,a[2011]={0},b[2011]={0},la,lb,dis,temp;
	char str[2011];
	scanf("%s",&str);
	la=strlen(str);
	for (i=1;i<=la;i++)
		a[i]=str[i-1];
	scanf("%s",&str);
	lb=strlen(str);
	for (i=1;i<=lb;i++)
		b[i]=str[i-1];
	scanf("%d",&dis);
	for (i=1;i<=la;i++)
	{
		f[0][i]=f[0][i-1]+dis;
		f[i][0]=f[i-1][0]+dis;
	}
	for (i=la+1;i<=lb;i++)
	{
		f[0][i]=f[0][i-1]+dis;
		f[i][0]=f[i-1][0]+dis;
	}
	for (i=1;i<=la;i++)
		for (j=1;j<=lb;j++)
		{
			f[i][j]=f[i-1][j-1]+absint(a[i]-b[j]);
			if (f[i-1][j]>f[i][j-1])
				temp=f[i][j-1];
			else
				temp=f[i-1][j];
			temp+=dis;
			if (temp<f[i][j])
				f[i][j]=temp;
		}
	printf("%d\n",f[la][lb]);
	fclose(stdin);
	fclose(stdout);
	return(0);
}