记录编号	410911	评测结果	AAAAAAAAAA
题目名称	字符串的距离	最终得分	100
用户昵称	FFF团	是否通过	通过
代码语言	C++	运行时间	0.141 s
提交时间	2017-06-02 21:37:49	内存使用	15.59 MiB

#include<bits/stdc++.h>
#include<string>
using namespace std;
const int maxn=2001;
string a,b;
int k;
int dp[maxn][maxn];
int main(){
	freopen("blast.in","r",stdin);
	freopen("blast.out","w",stdout);
	cin>>a>>b;
	scanf("\n%d",&k);
	//cout<<k<<endl;
	int l1=a.size();
	int l2=b.size();
	int l=max(l1,l2);
	memset(dp,0x7f,sizeof(dp));
	for(int i=0;i<l;i++){
		dp[i][0]=i*k;
		dp[0][i]=i*k;
	}
	/*
	for(int i=0;i<l;i++){
		cout<<dp[i][0]<<" "<<dp[0][i]<<endl;
	}
	*/
	for(int i=1;i<=l1;i++)
	for(int j=1;j<=l2;j++){
		int t=min(abs(a[i-1]-b[j-1]),2*k);
		dp[i][j]=min(dp[i-1][j-1]+t,min(dp[i][j-1]+k,dp[i-1][j]+k));
	}
	printf("%d\n",dp[l1][l2]);
	return 0;
}