自动搬运

查看原文

来自洛谷，原作者为

	AC_Evil 一竖一横，一撇一捺，是为AK也。 ——LX

搬运于2025-08-24 21:35:23，当前版本为作者最后更新于2020-10-15 15:31:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

状压DP

尤其注意到$m\leq 10$，那必然想到状压来求解。

状压$m$位二进制表示当前行中在矩形内的点为$1$，其余为$0$。

转移到下一行必须要满足题目内矩形的合法条件。

而判断需要$\mathcal O(m)$的复杂度。

总复杂度为$\mathcal O(nm\times 2^{2m})$，看起来很容易TLE，考虑做些有用的优化。

比如感性理解来看很多转移都是无用的（大概有$90\%$），这样常数就变成$1/10$。

再然后判断发现可以通过位运算直接$\mathcal O(1)$。

这样复杂度可以变成$\mathcal O(\frac1{10}\times n\times 2^{2m})$

细节请君看代码（又短又快又简洁/se）

#include <bits/stdc++.h>

const int B = 10, L = 205;

int f[1<<B], g[1<<B], n, m, c[L][B];
std::vector<int> tran[1<<B];

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			scanf("%d", &c[i][j]);
	for (int S = 0, U; S < 1<<m; S++)
		for (int T = 0; T < 1<<m; T++)
			if (U = S^T, !((U>>1|U<<1)&S&T)) tran[T].push_back(S);
	for (int i = 0; i < n; i++) {
		for (int S = 0; S < 1<<m; S++) {
			int sum = 0;
			for (int j = 0; j < m; j++) if (S&(1<<j)) sum += c[i][j];
			for (int j = 0; j < tran[S].size(); j++)
				g[S] = std::max(g[S], f[tran[S][j]] + sum);
		}
		memcpy(f, g, sizeof f); memset(g, 0, sizeof g);
	}
	int ans = 0;
	for (int S = 0; S < 1<<m; S++) ans = std::max(ans, f[S]);
	printf("%d", ans);
	return 0;
}