记录编号	166789	评测结果	AAAAAAAAAA
题目名称	字符串的距离	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.124 s
提交时间	2015-06-16 11:48:44	内存使用	15.60 MiB

#include<fstream>
#include<string>
#include<cstdlib>
 
using namespace std;
 
const int MAXN = 2002;
string s, t;
int dp[MAXN][MAXN], d;
ifstream fi("blast.in");
ofstream fo("blast.out");
#define cin fi
#define cout fo
 
main()
{
//	ios::sync_with_stdio(false);
	cin >> s >> t >> d;
	
    int n = s.size(), m = t.size();
    dp[0][0] = 0;
    for(int i = 1; i <= n; i ++)
        dp[i][0] = i * d;
    for(int i = 1; i <= m; i ++)
        dp[0][i] = i * d;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m;j ++)
            dp[i][j]=min(dp[i-1][j-1]+abs(s[i-1]-t[j-1]),
					 min(dp[i-1][j],dp[i][j-1])+d);
					 
    cout << dp[n][m];
}