题意：
给定一个$N imes M$的$01$矩阵，要求覆盖所有$1$的位置，求最小操作次数。一次操作，可以竖着覆盖连续的最多$C$列，或者横着覆盖连续的最多$R$行。
$1le;N,;M,;R,;Cle;15$
分析：
数据范围较小，考虑枚举。
但是不能盲目地同时枚举覆盖行、覆盖列的操作，因为这样的枚举是$O (2^{2N})$的，显然超时。
考虑枚举覆盖行的操作，枚得一种方案之后贪心地计算覆盖列的操作，完成。
总的时间复杂度$O (N^3 imes 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,&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(" "); } scanf("%d %d ",&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; }
小结：
考虑对枚举进行剪枝的同时，也考虑一下优化枚举的结构吧。