记录编号	31721	评测结果	AAAAAAAAAA
题目名称	字符串的距离	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.192 s
提交时间	2011-11-03 16:30:05	内存使用	15.55 MiB

#include<fstream>
#include<string.h>
using namespace std;

ifstream cin("blast.in");
ofstream cout("blast.out");

int ans[2001][2001],l1,l2,k;

char c1[2001],c2[2001];

int len(char c1,char c2)
{
	if(c1>c2)
	{
		return c1-c2;
	}
	else
	{
		return c2-c1;
	}
}

int min(int a,int b)
{
	return a<b?a:b;
}

int main()
{
	int i,j;
	cin>>c1>>c2>>k;
	l1=strlen(c1);
	l2=strlen(c2);
	for(i=1;i<=l1;i++)
		ans[0][i]=i*k;
	for(i=1;i<=l2;i++)
		ans[i][0]=i*k;
	for(i=1;i<=l2;i++)
	{
		for(j=1;j<=l1;j++)
		{
			ans[i][j]=min(k+min(ans[i-1][j],ans[i][j-1]),ans[i-1][j-1]+len(c1[j-1],c2[i-1]));
		}
	}
	cout<<ans[l2][l1]<<endl;
	return 0;
}