[USACO 2012 Mar Silver] Landscaping【Edit Distance】

传送门：http://www.usaco.org/index.php?page=viewproblem2&cpid=126

好题啊好题，一开始就输给了这道题的想法！

先把原始状态以及目标状态换一种表示方式，比如输入数据是的初始状态是1 2 3 4，表示成1 2 2 3 3 3 4 4 4 4，目标状态是4 3 2 0，表示成1 1 1 1 2 2 2 3 3。那么这题就是求把原始状态转化为目标状态的最小代价，只有三种操作， add, remove, transport，所以这就是一个求Edit Distance（编辑距离）的裸题！令f(i, j)表示初始状态的前i个转化为目标状态的前j个所需最小代价，则

f(i, j) = min( f(i - 1, j) + y, f(i, j - 1) + x, f(i - 1, j - 1) + z * abs(a[i] - b[j]) )

其中a[i]表示初始状态的第i个是什么，同理b[j]。

#include <cstdio>

#include <algorithm>

#include <cstring>

const int maxn = 105;

int n, a[1005], b[1005], idxa, idxb, f[1005][1005], x, y, z, t;

int main(void) {

	freopen("landscape.in", "r", stdin);

	freopen("landscape.out", "w", stdout);

	scanf("%d%d%d%d", &n, &x, &y, &z);

	memset(f, 0x3c, sizeof f);

	for (int i = 1; i <= n; ++i) {

		scanf("%d", &t);

		while (t--) {

			a[++idxa] = i;

		}

		scanf("%d", &t);

		while (t--) {

			b[++idxb] = i;

		}

	}

	for (int i = 1; i <= idxa; ++i) {

		f[i][0] = i * y;

	}

	for (int j = 1; j <= idxb; ++j) {

		f[0][j] = j * x;

	}

	f[0][0] = 0;

	for (int i = 1; i <= idxa; ++i) {

		for (int j = 1; j <= idxb; ++j) {

			f[i][j] = std::min(std::min(f[i - 1][j] + y, f[i][j - 1] + x), f[i - 1][j - 1] + z * std::abs(a[i] - b[j]));

		}

	}

	printf("%d\n", f[idxa][idxb]);

	return 0;

}

巴特西

[USACO 2012 Mar Silver] Landscaping【Edit Distance】

最新文章

热门文章