【题解】B4335 [中山市赛 2023] 互质
stellall
·
·
题解
题目大意
给定 n \times n 的矩阵，问放置若干个不重叠的 3 \times 3 子矩阵后，覆盖的每项元素的和最大是多少。
解题思路
由于是暴力搜索，所有我们要进行**一定的剪枝**，以防超时。
### 参考代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,a[20][20],ans;
pair<int, int> p[120];
int sum[110]={0};
bool v[15][15] = {0};
int dfs(int t,int maxx)//从第t个开始，maxx是相加的和
{
if(t==0)//当t=0，即表示所有子矩阵都深搜完
{//ans最大的和
ans=max(ans,maxx);//返回目前的和与最大的和哪个大，求最大值
return 0;
}
dfs(t-1,maxx);//情况1：不选该子矩阵
int x=p[t].first; //情况2：选
int y=p[t].second;
for(int i=x;i<=x+2;i++)
for(int j=y;j<=y+2;j++)
if (v[i][j]==1) //如果已经被选过了直接返回
return 0;
for(int i=x;i<=x+2;i++)
for(int j=y;j<=y+2;j++)
v[i][j]=1;//没选过，打上标记
dfs(t-1,maxx+sum[t]);//加上该矩阵的和，继续搜
for(int i=x;i<=x+2;i++)
for(int j=y;j<=y+2;j++)
v[i][j]=0;//回溯
return 0;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
int t=0;//子矩阵的数量
for(int i=1;i<=n-2;i++)
{
for(int j=1;j<=n-2;j++)
{
t++;
p[t]={i,j};//储存每个子矩阵的左上角的坐标
for(int x=i;x<=i+2;x++)
for(int y=j;y<=j+2;y++)
sum[t]+=a[x][y];//算出每个子矩阵的元素和
}
}
dfs(t,0);
cout<<ans;
return 0;
}
```
- 在最坏情况中，时间复杂度为 $O(2^{(n-2)^2})$。但实际运行时，由于重叠等原因，很多情况会被**提前剪枝**，因此实际运行时间远小于最坏情况（理论情况）。
- 所以该时间复杂度解决该题绰绰有余，不必担心。