分类存档：默认分类

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);
			}
    	}

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