题解：P11464 支配剧场

MaxDYF · 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();
    }
}