记录编号	80975	评测结果	AAAAAAAAAA
题目名称	字符串的距离	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.221 s
提交时间	2013-11-08 07:43:54	内存使用	18.70 MiB

#include<fstream>
#include<cstring>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fi("blast.in");
ofstream fo("blast.out");
string st1,st2;
int K,n,m;
int s1[2010],s2[2010];
int f[2010][2010];
int main()
{
	fi>>st1>>st2>>K;
	n=st1.size();
	for(int i=1;i<=n;i++)
		s1[i]=st1[i-1];
	m=st2.size();
	for(int i=1;i<=m;i++)
		s2[i]=st2[i-1];
	f[0][0]=0;
	for(int i=1;i<=n;i++)f[i][0]=K*i;
	for(int j=1;j<=m;j++)f[0][j]=K*j;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			f[i][j]=min(min(f[i][j-1]+K,f[i-1][j]+K),f[i-1][j-1]+abs(s1[i]-s2[j]));
	fo<<f[n][m]<<endl;
	return 0;
}