洛谷P11464 支配剧场

支配剧场

题目背景

May all the beauty be blessed.

题目描述

布洛妮娅和符华在寻找琪亚娜的途中，被支配之律者困在了支配剧场的高塔回廊之中。布洛妮娅敏锐地发现，虚无回廊是由一些支配之律者生成的积木构成的，只要击碎其中一些积木，就能解除空间的限制，让她们逃出高塔回廊。

具体来说，整个高塔回廊可以由一张高为 $n$，宽为 $m$ 的地图表示。第 $1$ 行为空间的最高点，第 $n$ 行为空间的最低点。高塔由 $K$ 块积木堆叠而成，符华每次可以击碎高塔中任意的积木，但必须保证高塔不会倒塌（否则她们会落入虚数空间），以及击碎积木后，高塔回廊的高度不变（即不能把最顶层的积木全部击碎）。

如果一块积木最底层的长度是 $L$，那么当且仅当其最底层与地板或者其他积木的接触面积 $L^{\prime }$ 满足 $L^{\prime }\ge \lceil \frac{L}{2}\rceil$ 时，这块积木不会失去平衡。当所有积木都不失去平衡时，我们认为整个高塔回廊不会倒塌。

积木的最底层长度被定义为积木行坐标最大的方块总个数。例如：

0 1 0
1 1 1
0 1 0

这张图中，$1$ 号积木的最底层长度是 $1$，因为其所占的格子中，行坐标最大的只有一个格子 $(3,2)$。

请帮布洛妮娅计算一下，符华最多能击碎多少个积木？

输入格式

第一行两个整数 $n,m$, 表示地图范围。

接下来 $n$ 行，每行 $m$ 个整数。第 $i$ 行第 $j$ 个整数 $a_{i,j}$，表示第 $i$ 行第 $j$ 列的格子属于第 $a_{i,j}$ 块积木。若 $a_{i,j}=0$，则这个位置是空的。

输出格式

一行一个整数，表示符华能击碎的最多的积木块数。

样例 #1

样例输入 #1

5 3
2 2 2
2 3 1
2 3 1
2 3 1
1 1 1

样例输出 #1

1

样例 #2

样例输入 #2

5 5
0 0 2 2 2
3 3 2 2 2
3 3 3 2 2
1 2 2 2 4
1 1 1 2 4

样例输出 #2

3

提示

$1\le n,m\le 30$，积木块数 $K$ 满足 $1\le K\le 15$，且保证高塔初始一定不会倒塌，同一块积木一定是一个四联通块。

【样例 1 解释】

符华可以击碎 $3$ 号积木，这不会导致高塔坍塌，也不会降低高塔的高度。可以证明没有更优的方案。

【样例 2 解释】

可以击碎 $1,3,4$ 号积木。

思路：

纯唐型，检查了一个小时为什么会WA，最后发现题目条件是要求塔的高度不能降低而不是塔高要为n。
n，m都较小，所以不需要太多算法，直接暴力dfs枚举可能删除积木的情况即可，就是实现的细节可能比较多…虽然考场上也没仔细想这个题，只觉得麻烦就放弃了去做别的，然后别的也没做出来。
另外，除夕夜了自己还在补题~，单纯是因为闲得无聊，那就祝看到这里的人新年快乐，蛇年大吉。

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
using namespace std;
int a[35][35];
int k[50],bj[50];
vector<int> c;
int ans  = 0 ;
int n,m,cnt=0;
vector<int>bh;
int cbh[50];
int hst=0;
bool check(){// cout<<"check:";// for(int e:c)cout<<e<<" ";// cout<<endl;if(c.size()==0)return false;bool bd = 0;for(int i=1;i<=m;i++){if(bj[a[hst][i]]){bd=1;// cout<<"wd"<<endl;break;}}if(!bd) return false;for(int e : c){if(k[e]==n)continue;int cd=0,cj=0;    for(int i=1;i<=m;i++){ if(a[k[e]][i] == e){cd++;if(bj[a[k[e]+1][i]])cj++;}}// cout<<e<<" "<<cj<<" "<<cd<<endl;if(cj*2<cd){bd=0;break;}}return bd;
}void dfs(int cz,int x){if(x==cnt){if(cz!=0 && check()){// cout<<"-cg : "<<cnt-cz<<endl;ans = max(ans,cnt-cz);}return;};bj[bh[x+1]]=1;c.push_back(bh[x+1]);dfs(cz+1,x+1);bj[bh[x+1]]=0;c.pop_back();dfs(cz,x+1);
}signed main() {cin.tie(0)->ios::sync_with_stdio(0);cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){cin>>a[i][j];if(hst ==0 && a[i][j]!=0 )hst = i;if(cbh[a[i][j]]==0){bh.push_back(a[i][j]);cbh[a[i][j]]=1;}}}if(cbh[0]==0)bh.push_back(0);cnt = bh.size()-1;sort(bh.begin(),bh.end());for(int i=n;i>=1;i--){for(int j=1;j<=m;j++){if(k[a[i][j]] == 0){k[a[i][j]]=i;}}}dfs(0,0);cout<<ans;// cout<<endl<<a[1][5]<<" "<<bj[a[1][5]];return 0;
}