题意：有一个 \(H\times W\) 的地板和 \(n\) 个矩形地毯，问是否能不重不漏地填满地板。\(H,W\le 100,n\le 7\)。
考虑朴素的搜索，每次考虑最左上角的没填的位置，枚举用哪块地毯覆盖（因为这个格子肯定需要被覆盖，而不可能被更左上的格子覆盖）。先检查是否可以用这块地毯，如果可以用则把这块地毯填上，继续搜索，回溯时撤销操作。
这样虽然可以通过本题，但速度比较慢，考虑剪枝。思考可以发现，大多数情况下面积根本无法凑到恰好 \(H\times
W\)，所以可以提前枚举用哪些地毯，如果这个地毯集合能凑到恰好 \(H\times W\)
的面积，就强行钦定只能用这些地毯再搜索。代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
struct node{int x,y;} a[10];
bool vis[10],cov[110][110];
void dfs() {
int x=-1,y=-1;
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++)
if(!cov[i][j]) {
x=i,y=j;
break;
}
if(x!=-1) break;
}
if(x==-1) {
cout<<"yes"<<endl;
exit(0);
}
for(int j=1;j<=q;j++) {
if(vis[j]) continue;
vis[j]=1;
for(int t=0;t<=1;t++,swap(a[j].x,a[j].y)) {
bool flag=1;
for(int xx=x;xx<x+a[j].x;xx++)
for(int yy=y;yy<y+a[j].y;yy++)
if(xx>n||yy>m||cov[xx][yy]) flag=0;
if(flag) {
for(int xx=x;xx<x+a[j].x;xx++)
for(int yy=y;yy<y+a[j].y;yy++)
cov[xx][yy]=1;
dfs();
for(int xx=x;xx<x+a[j].x;xx++)
for(int yy=y;yy<y+a[j].y;yy++)
cov[xx][yy]=0;
}
}
vis[j]=0;
}
}
signed main() {
cin>>n>>m>>q;
int tot=0;
for(int i=1;i<=q;i++) {
int num,x,y;
cin>>num>>x>>y;
while(num--) a[++tot]={x,y};
}
q=tot;
for(int s=1;s<(1<<q);s++) {
int sum=0;
for(int i=1;i<=q;i++)
if(s&(1<<(i-1))) sum+=a[i].x*a[i].y;
else vis[i]=1;
if(sum==n*m) dfs();
for(int i=1;i<=q;i++) vis[i]=0;
}
cout<<"no"<<endl;
return 0;
}
加了这个优化后可以达到 100ms 以内，但离最优解还有一定距离。接下来我加的优化为改变搜索的内容。
我们在搜索的过程中钦定从左上角开始填，记录当前的轮廓线（可以用链表维护）。每次枚举每个拐角来添加地毯。添加的时候要求添加后仍然为从右上到左下的一条折线。这一步的正确性是有保证的，因为最终的解一定能通过这个限制搜到，原因是，如果最终解中每个拐角填的地毯都不为一条折线，那么考虑最右上的拐角，它显然不能往右超出这个拐角的范围，只能往下。而右上的第二个拐角由于右边被第一个拐角超出挡住，所以只能往下。以此类推到最后一个拐角也只能往下，而这显然是不可能的。所以最终解一定能通过这个限制被搜到。
用这个搜索方式加上面的剪枝就拿到了 15ms 的最优解。
By cxm1024
#include<bits/stdc++.h>
using namespace std;
int n,m,q;
struct node{int x,y;} a[10];
bool vis[10];
pair<int,int> now[20];
int head,tail,lst[20],nxt[20],cnt=0;
void dfs() {
if(nxt[head]==tail) {
cout<<"yes"<<endl;
exit(0);
}
for(int i=nxt[head];i!=tail;i=nxt[i]) {
int fir=now[i].first,sec=now[i].second;
for(int j=1;j<=q;j++) {
if(vis[j]) continue;
for(int t=0;t<=1;t++,swap(a[j].x,a[j].y)) {
if(a[j].x>fir||a[j].y>sec) continue;
vis[j]=1;
if(a[j].x==fir&&a[j].y==sec) {
now[nxt[i]].first+=fir,now[lst[i]].second+=sec;
nxt[lst[i]]=nxt[i],lst[nxt[i]]=lst[i];
dfs();
now[nxt[i]].first-=fir,now[lst[i]].second-=sec;
nxt[lst[i]]=i,lst[nxt[i]]=i;
}
else if(a[j].x==fir) {
now[i].second-=a[j].y,now[lst[i]].second+=a[j].y;
dfs();
now[i].second+=a[j].y,now[lst[i]].second-=a[j].y;
}
else if(a[j].y==sec) {
now[i].first-=a[j].x,now[nxt[i]].first+=a[j].x;
dfs();
now[i].first+=a[j].x,now[nxt[i]].first-=a[j].x;
}
else {
now[++cnt]={fir-a[j].x,a[j].y};
nxt[lst[i]]=cnt,lst[cnt]=lst[i];
now[++cnt]={a[j].x,sec-a[j].y};
lst[cnt]=cnt-1,nxt[cnt-1]=cnt;
nxt[cnt]=nxt[i],lst[nxt[i]]=cnt;
dfs();
lst[nxt[i]]=i,nxt[lst[i]]=i,cnt-=2;
}
vis[j]=0;
}
}
}
}
signed main() {
cin>>n>>m>>q;
int tot=0;
for(int i=1;i<=q;i++) {
int num,x,y;
cin>>num>>x>>y;
while(num--) a[++tot]={x,y};
}
q=tot;
head=++cnt,tail=++cnt;
now[++cnt]={m,n},lst[cnt]=head,nxt[cnt]=tail;
nxt[head]=cnt,lst[tail]=cnt;
for(int s=1;s<(1<<q);s++) {
int sum=0;
for(int i=1;i<=q;i++)
if(s&(1<<(i-1))) sum+=a[i].x*a[i].y;
else vis[i]=1;
if(sum==n*m) dfs();
for(int i=1;i<=q;i++) vis[i]=0;
}
cout<<"no"<<endl;
return 0;
}