Java教程

P1279 字串距离

本文主要是介绍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] << '\n';
}
这篇关于P1279 字串距离的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航