自动搬运

查看原文

来自洛谷，原作者为

	MaxDYF **

搬运于2025-08-24 23:07:36，当前版本为作者最后更新于2024-12-24 14:29:23，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

注意到这题的 $n,m,K$ 的限制都很小，可以考虑 DFS 暴力搜索。

我们枚举最后删掉了哪些积木，然后在最后检查删掉这些积木后，剩下的积木是否能不失去平衡。一种比较好的检查方法是，提前将每个积木的最底部位置存起来，然后检查的时候只遍历没有被删掉的积木的最底端的下一层是否有支撑。

单次检查的时间复杂度为 $\Theta(mk)$，总的时间复杂度为 $\Theta(mk2^k)$。单次检查复杂度为 $\Theta(nm)$ 的算法也可通过此题。

Code

// #pragma GCC optimize("Ofast,no-stack-protector")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

const int N = 50;
const int inf = 1 << 30;
const ll inf64 = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x & -x)

int n, m, k, q;
int a[N][N];
vector<pii> tot[N];
bool ban[N];
void toggle(int c)
{
	for (auto [x, y] : tot[c])
		a[x][y] = -a[x][y];
	ban[c] = !ban[c];
}
int highest;
int lowest[N], cnt[N];
bool check()
{
	for (int i = 1; i <= k; i++)
	{
		if (lowest[i] == 0 || ban[i])
			continue;
		int cnt0 = 0;
		for (int j = 0; j < m; j++)
			cnt0 += (a[lowest[i]][j] == i) && (a[lowest[i] - 1][j] > 0);
		if (cnt0 < (cnt[i] + 1) / 2)
			return false;
	}
	for (int j = 0; j < m; j++)
		if (a[highest][j] > 0)
			return true;
	return false;
}
int ans;
void dfs(int x = 1, int cnt = 0)
{
	if (cnt + (k - x + 1) <= ans)
		return;
	if (x == k + 1)
	{
		if (check())
			ans = max(ans, cnt);
		return;
	}
	toggle(x);
	dfs(x + 1, cnt + 1);
	toggle(x);
	dfs(x + 1, cnt);
}
void work()
{
	cin >> n >> m;
	for (int i = n - 1; i >= 0; i--)
		for (int j = 0; j < m; j++)
		{
			cin >> a[i][j];
			if (a[i][j])
				highest = max(highest, i);
			k = max(k, a[i][j]);
			if (!a[i][j])
				continue;
			if (lowest[a[i][j]] == i)
				cnt[a[i][j]]++;
			else
			{
				lowest[a[i][j]] = i;
				cnt[a[i][j]] = 1;
			}
			tot[a[i][j]].push_back({i, j});
		}
	dfs();
	cout << ans << endl;
}
int main()
{
	cin.tie(nullptr)->sync_with_stdio(false);
	int t = 1;
	while (t-- > 0)
	{
		work();
	}
}