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

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
/*
A,B下标从1开始
f[i][j]表示A[i]正对B[j]的最小值
g[i][j]表示A[i]正对B[j]和B[j+1]之间某个空格的最小值
h[j][i]表示B[i]正对A[j]和A[j+1]之间某个空格的最小值
特别的,g[i][0]和h[0][i]表示前i个对上一个全为空格的串
g[0][0]=h[0][0]=0
g[i][0]=g[i-1][0]+(A[i]与空格距离)
h[0][i]=h[0][i-1]+(B[i]与空格距离)
f[i][0]=g[i][0],f[0][i]=h[0][i]
f[i][1]=g[i-1][0]+(A[i]与B[1]的距离)
f[1][i]=h[0][i-1]+(A[1]与B[i]的距离)
f[i][j],则前面一对不可能是全空格
故f[i][j]=(A[i]与B[j]距离)+min(f[i-1][j-1],g[i-1][j-1],h[i-1][j-1])
g[i][j]=(A[i]与空格距离)+min(f[i-1][j],g[i-1][j],h[i-1][j])
h[i][j]=(B[j]与空格距离)+min(f[i][j-1],g[i][j-1],h[i][j-1])
*/
const int INF=0x7ffffff;
const int SIZEL=2001;
int K;
string A,B;
int lena,lenb;
int f[SIZEL][SIZEL]={0},g[SIZEL][SIZEL]={0},h[SIZEL][SIZEL]={0};
void init(void){
	int i,j;
	for(i=0;i<=lena;i++){
		for(j=0;j<=lenb;j++) f[i][j]=g[i][j]=h[i][j]=INF;
	}
	f[0][0]=g[0][0]=h[0][0]=0;
	for(i=1;i<=lena;i++) f[i][0]=g[i][0]=g[i-1][0]+K;
	for(j=1;j<=lenb;j++) f[0][j]=h[0][j]=h[0][j-1]+K;
}
int min(int &a,int &b,int &c){
	int ans=a;
	ans=min(ans,b);
	ans=min(ans,c);
	return ans;
}
void DP(void){
	int i,j;
	for(i=1;i<=lena;i++){
		for(j=1;j<=lenb;j++){
			f[i][j]=abs(A[i]-B[j])+min(f[i-1][j-1],g[i-1][j-1],h[i-1][j-1]);
			g[i][j]=K+min(f[i-1][j],g[i-1][j],h[i-1][j]);
			h[i][j]=K+min(f[i][j-1],g[i][j-1],h[i][j-1]);
		}
	}
}
void read(void){
	cin>>A>>B;
	lena=A.size(),lenb=B.size();
	A=" "+A,B=" "+B;
	scanf("%d",&K);
}
int main(){
	freopen("blast.in","r",stdin);
	freopen("blast.out","w",stdout);
	read();
	init();
	DP();
	printf("%d\n",min(f[lena][lenb],g[lena][lenb],h[lena][lenb]));
	return 0;
}