题目链接
题意：
给定一个$N\times M$的$01$矩阵，要求覆盖所有$1$的位置，求最小操作次数。一次操作，可以竖着覆盖连续的最多$C$列，或者横着覆盖连续的最多$R$行。
$1\le\;N,\;M,\;R,\;C\le\;15$
分析：
数据范围较小，考虑枚举。
但是不能盲目地同时枚举覆盖行、覆盖列的操作，因为这样的枚举是$O (2^{2N})$的，会$T$。
考虑枚举覆盖行的操作，枚得一种方案之后贪心地计算覆盖列的操作，完成。
总的时间复杂度$O (N^3\times 2^N)$。
实现：
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define IL inline
using namespace std;
const int N=
15;
int n,m,r,c;
int bod[N+
3][N+
3];
int clm[N+
3];
int tbod[N+
3][N+
3];
int tclm[N+
3];
int main(){
scanf("%d %d\n",&n,&
m);
memset(bod,0,
sizeof bod);
for(
int i=
0;i<n;i++
){
char ch;
for(
int j=
0;j<m;j++
){
scanf("%c",&
ch);
bod[i][j]=ch==
'X';
}
scanf("\n");
}
scanf("%d %d\n",&r,&
c);
memset(clm,0,
sizeof clm);
for(
int i=
0;i<m;i++
)
for(
int j=
0;j<n;j++
)
clm[i]+=
bod[j][i];
memcpy(tbod,bod,sizeof bod);
memcpy(tclm,clm,sizeof clm);
int ans=min(n/r+
1,m/c+
1);
for(
int S=
0;S<(
1<<n);S++
){
int cnt=
0;
for(
int i=
0;i<n;i++
)
if(S>>i&
1){
cnt++
;
for(
int j=
0;j<r;j++
)
for(
int k=
0;k<m;k++
)
if(bod[i+j][k]==
1){
bod[i+j][k]=
0;
clm[k]--
;
}
}
for(
int i=
0;i<m;i++
)
if(clm[i]>
0){
cnt++
;
for(
int j=
0;j<c;j++
)
clm[i+j]=
0;
}
memcpy(bod,tbod,sizeof tbod);
memcpy(clm,tclm,sizeof tclm);
ans=
min(ans,cnt);
}
printf("%d",ans);
return 0;
}
View Code
小结：
考虑对枚举进行剪枝的同时，也考虑一下优化枚举的结构吧。
转载于:https://www.cnblogs.com/Hansue/p/11369362.html
相关资源：JAVA上百实例源码以及开源项目
