记录编号	27426	评测结果	AAAAAAAAAA
题目名称	字符串的距离	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	C++	运行时间	0.299 s
提交时间	2011-09-22 14:08:35	内存使用	15.68 MiB

#include <iostream>
#include <fstream>
#include <string>

using namespace std;

int i,j,k,l,n,m,kk;
string a,b;
char c,d;
int f[2010][2010];

int Abs(int x)
{
	if (x>0)
		return x;
	return -x;
}

int main()
{
	ifstream fin("blast.in");
	ofstream fout("blast.out");
	
	getline(fin,a);
	getline(fin,b);
	fin>>kk;
	
	n=a.length();
	m=b.length();
	
	f[0][0]=0;
	f[0][1]=kk;
	f[1][0]=kk;
	for (i=2;i<=n;i++)
		f[i][0]=kk*i;
	for (j=2;j<=m;j++)
		f[0][j]=kk*j;
	
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
		{
			f[i][j]=f[i-1][j-1]+Abs(int(a[i-1])-int(b[j-1]));
			if ((f[i][j-1]+kk)<f[i][j])
				f[i][j]=f[i][j-1]+kk;
			if ((f[i-1][j]+kk)<f[i][j])
				f[i][j]=f[i-1][j]+kk;
		}
	
	fout<<f[n][m]<<endl;
	
	fin.close();
	fout.close();
	
	return 0;
}