我们可以发现如果a,b都加空格的话,是没有意义的。因此我们一共有三种状态(i ->a ,j ->b)
i填空格,j填空格,都不填空格。枚举即可
char a[N], b[N];
int la, lb;
int k;
int f[N][N];
int main() {
cin >> (a + 1) >> (b + 1) >> k;
la = strlen(a + 1);
lb = strlen(b + 1);
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
rep(i, 1, la) {
f[i][0] = i * k;
}
rep(i, 1, lb) {
f[0][i] = i * k;
}
rep(i, 1, la) {
rep(j, 1, lb) {
f[i][j] = min(min(f[i][j], f[i-1][j-1] + abs(a[i] - b[j])), min(f[i - 1][j] + k, f[i][j - 1] + k));
}
}
cout << f[la][lb] << '\n';
}