题目链接：点这里！！！
题意：中文题。
题解：做的第一道DLX重复覆盖，我们把1当成一列，每个枚举的矩阵当成行，然后跑DLX重复覆盖就可以了！！！！
（不过不是很懂他的剪枝函数）
代码：
<span style="font-family:SimHei;font-size:14px;">#include<</span>cstdio> #include<cstring> #include<iostream> #include<sstream> #include<algorithm> #include<vector> #include<bitset> #include<set> #include<queue> #include<stack> #include<map> #include<cstdlib> #include<cmath> #define pb push_back #define pa pair<int,int> #define clr(a,b) memset(a,b,sizeof(a)) #define lson lr<<1,l,mid #define rson lr<<1|1,mid+1,r #define bug(x) printf("%d++++++++++++++++++++%d\n",x,x) #define key_value ch[ch[root][1]][0] #pragma comment(linker, "/STACK:102400000000,102400000000") typedef long long LL; const LL MOD = 1000000007; const int N = 55; const int maxn = 1e6+15; const int letter = 130; const int INF = 1e9; const double pi=acos(-1.0); const double eps=1e-10; using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,n1,m1; int mp[20][20]; int pc; const int maxnode = 15*15*15*15+15; const int maxh=15*15+15; struct dlx{ int n,m,size; int U[maxnode],D[maxnode],L[maxnode],R[maxnode]; int row[maxnode],col[maxnode]; int H[maxh],S[maxh]; int ansd,ans[maxh]; bool v[maxnode]; void init(int _n,int _m){ n=_n,m=_m; for(int i=0;i<=m;i++){ S[i]=0; U[i]=D[i]=i; L[i]=i-1; R[i]=i+1; } R[m]=0,L[0]=m; size=m; for(int i=1;i<=n;i++) H[i]=-1; } void link(int r,int c){ ++S[col[++size]=c]; row[size]=r; D[size]=D[c]; U[D[c]]=size; U[size]=c; D[c]=size; if(H[r]<0) H[r]=L[size]=R[size]=size; else { R[size]=R[H[r]]; L[R[H[r]]]=size; L[size]=H[r]; R[H[r]]=size; } } void remove(int c){ L[R[c]]=L[c],R[L[c]]=R[c]; for(int i=D[c];i!=c;i=D[i]) for(int j=R[i];j!=i;j=R[j]){ U[D[j]]=U[j]; D[U[j]]=D[j]; --S[col[j]]; } } void resume(int c){ for(int i=U[c];i!=c;i=U[i]) for(int j=L[i];j!=i;j=L[j]) ++S[col[U[D[j]]=D[U[j]]=j]]; L[R[c]]=R[L[c]]=c; } ///重复覆盖 void remove_1(int c){ for(int i=D[c];i!=c;i=D[i]){ L[R[i]]=L[i],R[L[i]]=R[i]; } } void resume_1(int c){ for(int i=U[c];i!=c;i=U[i]) L[R[i]]=i,R[L[i]]=i; } int f(){ int sum=0; for(int c=R[0];c!=0;c=R[c]) v[c]=1; for(int c=R[0];c!=0;c=R[c]){ if(v[c]){ sum++; v[c]=0; for(int i=D[c];i!=c;i=D[i]) for(int j=R[i];j!=i;j=R[j]) v[col[j]]=0; } } return sum; } void dance_1(int d){ if(d+f()>=pc) return; if(R[0]==0){pc=min(pc,d);return;} int c=R[0]; for(int i=R[0];i!=0;i=R[i]) if(S[i]<S[c]) c=i; for(int i=D[c];i!=c;i=D[i]){ remove_1(i); for(int j=R[i];j!=i;j=R[j]) remove_1(j); dance_1(d+1); for(int j=L[i];j!=i;j=L[j]) resume_1(j); resume_1(i); } } bool dance(int d){ if(R[0]==0){ansd=d;return true;} int c=R[0]; for(int i=R[0];i!=0;i=R[i]) if(S[i]<S[c]) c=i; remove(c); for(int i=D[c];i!=c;i=D[i]){ ans[d]=row[i]; for(int j=R[i];j!=i;j=R[j]) remove(col[j]); if(dance(d+1)) return true; for(int j=L[i];j!=i;j=L[j]) resume(col[j]); } resume(c); return false; } }cc; int main(){ while(~scanf("%d%d",&n,&m)){ int cnt=0; pc=INF; clr(mp,0); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ scanf("%d",&mp[i][j]); if(mp[i][j]) mp[i][j]=++cnt; } scanf("%d%d",&n1,&m1); cc.init((n-n1+1)*(m-m1+1),cnt); int siz=1; for(int i=1;i<=n-n1+1;i++) for(int j=1;j<=m-m1+1;j++){ for(int x=i;x<i+n1;x++){ for(int y=j;y<j+m1;y++){ if(mp[x][y]){ cc.link((i-1)*(m-m1+1)+j,mp[x][y]); } } } siz++; } cc.dance_1(0); printf("%d\n",pc); } return 0; } /* 4 4 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 4 1 */