搜索基础 - “黄尘清水三山下”
2026-07-15 07:46:15
发布于：浙江
2阅读
0回复
0点赞
自学笔记类产物
黄尘清水三山下，更变千年如走马。——李贺《梦天》
https://www.luogu.com.cn/problem/P1034
P1034矩阵覆盖
这道题目还是相对来说一眼暴搜的。毕竟。
另外怎么算这个时间复杂度是个好问题。
五十个点，挨个枚举它们应该放在哪个方形里面。
每个点都有k种选择。
那是大概是。
那它为什么能拥暴力搜索过呢？
因为有剪枝。
剪枝到底减了多少我们无从可知，只能尽量祈祷。
其次，另一个难点就是判断两个矩形之间有没有交点。
判断交点的方法就是看两个矩形在垂直方向和水平方向上有没有相交。
放个代码：
#include<bits/stdc++.h>
using namespace std;
const int N=5e2+5;
int x[N],y[N],n,k;
struct Node{
int a,b,c,d;
}node[N];
int ans=INT_MAX;
bool check(int u){
for(int i=1;i<=k;i++){
if(u==i)continue;
if(node[i].a==0&&node[i].b==0&&node[i].c==0&&node[i].d==0)continue;
if((node[u].a<=node[i].b&&node[u].b>=node[i].a)&&(node[u].c<=node[i].d&&node[i].c<=node[u].d)){
return 0;
}
}
return 1;
}
void dfs(int u){
int sum1=0;
for(int i=1;i<=k;i++){
sum1+=(node[i].b-node[i].a)*(node[i].d-node[i].c);
}
if(sum1>=ans)return;
if(u>n){
int sum=0;
for(int i=1;i<=k;i++){
sum+=(node[i].b-node[i].a)*(node[i].d-node[i].c);
}
ans=min(ans,sum);
return;
}
for(int i=1;i<=k;i++){
Node sum=node[i];
if(node[i].a==0){
node[i].a=x[u];
}else node[i].a=min(node[i].a,x[u]);
if(node[i].c==0){
node[i].c=y[u];
}else node[i].c=min(node[i].c,y[u]);
node[i].b=max(node[i].b,x[u]);
node[i].d=max(node[i].d,y[u]);
if(check(i))dfs(u+1);
node[i]=sum;
}
return;
}
int main(){
cin>>n>>k;
for(int i=1;i<=n;i++)cin>>x[i]>>y[i],x[i]++,y[i]++;
dfs(1);
cout<<ans;
return 0;
}
马上要考试了，等我回来做总结吧。
这里空空如也
有帮助，赞一个