Gym100753D-Carpets题解

发表于 分类于

题目传送门

题意：有一个 H×WH\times W 的地板和 nn 个矩形地毯，问是否能不重不漏地填满地板。H,W≤100,n≤7H,W\le 100,n\le 7。

考虑朴素的搜索，每次考虑最左上角的没填的位置，枚举用哪块地毯覆盖（因为这个格子肯定需要被覆盖，而不可能被更左上的格子覆盖）。先检查是否可以用这块地毯，如果可以用则把这块地毯填上，继续搜索，回溯时撤销操作。

这样虽然可以通过本题，但速度比较慢，考虑剪枝。思考可以发现，大多数情况下面积根本无法凑到恰好 H×WH\times W，所以可以提前枚举用哪些地毯，如果这个地毯集合能凑到恰好 H×WH\times W
的面积，就强行钦定只能用这些地毯再搜索。代码如下：

By cxm1024 From lqs2015

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#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;
}