1 #include<bits/stdc++.h> 2 using namespace std; 3 const int N=3000; 4 char c1[N],c2[N]; 5 int l1,l2,d[N][N],k; 6 int main() { 7 scanf("%s", c1); 8 scanf("%s", c2); 9 l1 = strlen(c1); 10 l2 = strlen(c2); 11 scanf("%d", &k); 12 for (int i = 1; i <= l1; i++) { 13 d[i][0] = d[i - 1][0] + k; 14 } 15 for (int i = 1; i <= l2; i++) { 16 d[0][i] = d[0][i - 1] + k; 17 } 18 for (int i = 1; i <= l1; i++) { 19 for (int j = 1; j <= l2; j++) { 20 d[i][j] = min(d[i - 1][j] + k, d[i][j - 1] + k); 21 d[i][j] = min(d[i][j], d[i - 1][j - 1] + abs(c1[i - 1] - c2[j - 1])); 22 } 23 } 24 printf("%d ", d[l1][l2]); 25 }