SRM 577

250pt
略,小心写就好。

500pt

给一个8 * 8的方格,某些格子为#要填东西。每次填一个格子,cost是已填格子里离本格子Manhattan distance最远的点的Manhattan distance。问填出给定的pattern最少需要的代价。

一个奇怪的技巧,Manhattan distance将坐标旋转45°((x,y) -> (x + y, x – y) ———— 记为(p, q))以后,就从
$$abs(x_1 – x_2) + abs(y_1 – y_2)$$ 变为 $$max(abs(p_1 – p_2), abs(q_1 – q_2))$$
因为从+变成了max,所以可以dp了……因为只需要记录已填区域的minx, maxx, miny, maxy就可以转移。

1000pt

给定一个pattern,某些地方要涂上颜色,每次可以用一横或者一竖将一系列没有被涂过颜色的点涂上色。问最少要涂多少笔。

-_-官方题解的建图看着真是太挫了……
关键就在于要给每个要涂色的点分一个状态Down或Right. 而如果我是Down,下面不是一个为Down的点(没有也不算是),那么ans++,如果我是Right,但右边的点不是Right(没有也不算是),ans++。
所以假设每个格子对应一个点,他被割在S一边表示Down的状态,割在T一边表示Right的状态,那么建边就像这样。

    	rep (i, m) rep (j, n) {
    		if (target[i][j] != '#') continue;
			if (i + 1 < m && target[i + 1][j] == '#') {
				addedge(id[i][j], id[i + 1][j], 1);
			} else {
				addedge(id[i][j], T, 1);
			}
			if (j + 1 < n && target[i][j + 1] == '#') {
				addedge(id[i][j + 1], id[i][j], 1);
			} else {
				addedge(S, id[i][j], 1);
			}
    	}

跑一遍最小割就可以得到答案。

加入对话

2条评论

    1. 之前是+的时候,新加入一个点必须知道之前的整个点集才可以算出这个点Manhattan distance最远的是多少。
      变成max了以后,新的点要算 Manhattan distance,只需要知道minp, maxp, minq, maxq这4个参数就够了。

留下评论

您的电子邮箱地址不会被公开。 必填项已用 * 标注