P1279 字串距离

我们可以发现如果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] << '
';
}