CWOI S C0281 D 棋盘

题意

使用 openssl enc -aes256 -pbkdf2 -a 加密。

U2FsdGVkX187NyPTtVajyNS83bfTBw+nUU2o4e8EMUgKvXl3lwqKBx+mKL4/LWqp
tuz8INyEYPSMAW9pnFaJEDnDbOLE5/eipbg+Zg3LCtGLZTR5f08XRiW5wlyS/ROj
aF7imQPtHAxG7d19V4U2eU/K8mctdqYv4pXa0CYnUn1015MBJlg0XkqQiNBo7STM
r+/vdnIdLT7bS2ipAjdOD09DfeRMqyAWBxX/xhtUBi1mQ+oZ52AZz4ug44znYlMb
ZwTBuMzP1nLuJeLWkzfVxPaerBYCG6EvEBW/SyVLAlTUj7PYjwVssXnlxYn3pDPA
C8+8gZsz9EyyePz6pE5JjQ==

解析

关于 Manhattan 距离，有一个常见的 trick，即如果一个点为 $(x, y)$，则可以转化为 $(x', y') = (x + y, x - y)$，这样 $|x_1-x_2|+|y_1-y_2|$ 就可以变为 $\max\{|x'_1-x'_2|, |y'_1-y'_2|\}$。前者为 Manhattan 距离，后者为 Chebyshev 距离。

首先我们先将棋盘上所有点的坐标按照上面的方法转换成可以用 Chebyshev 距离计算的坐标。对于转换完的点，令 $f(S)$ 表示点集为 $S$ 时最小代价。

我们在 $S$ 中找到 $x$ 最大、最小，$y$ 最大、最小的点，这里我们分别记作 B、D、A、 C（如果有多个一样大就随便找一个）。如果 $x_B - x_D > y_A - y_C$，那么我们就从 $f(S \setminus B)$ 和 $f(S \setminus D)$ 中转移；如果 $x_B - x_D < y_A - y_C$，那么我们就从 $f(S \setminus A)$ 和 $f(S \setminus C)$ 中转移。如果相等，就随便。

这样做是正确的，以 $x_B - x_D > y_A - y_C$ 为例，可以肯定的是 $x_B - x_D$ 这个一定会在某次计算代价时被计算到。而对于 $B$ 和 $D$ 以外的点，如果我们先把 $B$ 或 $D$ 删除了，删除他们的代价会变小，总的来说，先删除 $B$ 或 $D$ 不劣。

同时时间复杂度也是正确的。考虑将 $(x, y)$ 转换成 $(x + y, x - y)$ 之后，最极限的情况，一条边上最多有 4 个点，这个删点的过程，从某个矩形删成缩小的矩形，状态数是 $2^4 \times 2^4$，即像对两条矩形边上的点数相乘。最多可能的矩形数量是 $16^4$ 级别的。所以总共状态数上界是 $2^8 \times 16^4$，而且不可能卡满。

实现

int main()
{
	std::vector<std::pair<int, int>> dot;
	for (int i = 0; i < 8; i++) {
		for (int j = 0; j < 8; j++) {
			char ch;
			std::cin >> ch;
			if (ch == '#') dot.emplace_back(i + j, i - j);
		}
	}

	std::map<std::vector<std::pair<int, int>>, int> f;

	auto comp_first = [](std::pair<int, int> a, std::pair<int, int> b)
	{
		return a.first < b.first;
	};
	auto comp_second = [](std::pair<int, int> a, std::pair<int, int> b)
	{
		return a.second < b.second;
	};
	
	auto dfs = [&f, comp_first, comp_second](auto &&self, std::vector<std::pair<int, int>> dot) -> int
	{
		if (dot.size() <= 1) return 0;
		if (f.contains(dot)) return f[dot];

		auto min_first = std::min_element(dot.begin(), dot.end(), comp_first);
		auto max_first = std::max_element(dot.begin(), dot.end(), comp_first);
		auto min_second = std::min_element(dot.begin(), dot.end(), comp_second);
		auto max_second = std::max_element(dot.begin(), dot.end(), comp_second);

		auto res = std::numeric_limits<int>::max();

		auto wfirst = max_first->first - min_first->first;
		auto wsecond = max_second->second - min_second->second;
		if (wfirst > wsecond) {
			{
				auto backup = dot;
				dot.erase(min_first);
				res = std::min(res, self(self, dot) + wfirst);
				dot = backup;
			}
			{
				auto backup = dot;
				dot.erase(max_first);
				res = std::min(res, self(self, dot) + wfirst);
				dot = backup;
			}
		} else {
			{
				auto backup = dot;
				dot.erase(min_second);
				res = std::min(res, self(self, dot) + wsecond);
				dot = backup;
			}
			{
				auto backup = dot;
				dot.erase(max_second);
				res = std::min(res, self(self, dot) + wsecond);
				dot = backup;
			}
		}

		f[dot] = res;
		return res;
	};

	std::cout << dfs(dfs, dot) << std::endl;
}