CF142C-Help-Caretaker题解

发表于 分类于

题目传送门

题意：有一个 n×mn\times m 的矩阵，用尽可能多的“T”形覆盖它（可以旋转），使得它们之间互不重叠。

可以搜索，每次考虑当前位置放哪个角度的“T”形，转移到下一个位置。主要进行最优性剪枝：如果当前填放的数量加上之后的极大值（剩余格子数 ÷5\div 5）则直接返回。还有一个启发性剪枝，即左上角一定要放一个正着的“T”或往左歪的“T”。

最优性剪枝还有另一种形式：记录前 ii 行能填的最大数量 best[i]best[i]，每次填完一行后如果和 best[i]best[i] 差的过大则返回。

第一种 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
74
75
76
#include<bits/stdc++.h>
using namespace std;
int n,m,bst=0;
char now[15][15],ans[15][15];
int dx[4][5]={
    {0,-1,-2,-2,-2},
    {0,-1,-1,-1,-2},
    {0,0,0,-1,-2},
    {0,-1,-1,-1,-2}
};
int dy[4][5]={
    {-1,-1,0,-1,-2},
    {0,0,-1,-2,0},
    {0,-1,-2,-1,-1},
    {-2,0,-1,-2,-2}
};
void dfs(int x,int y,char ch) {
    if(y>m) {
        dfs(x+1,3,ch);
        return;
    }
    if(x>n) {
        if(ch-'A'>bst) {
            bst=ch-'A';
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    ans[i][j]=now[i][j];
        }
        return;
    }
    if(ch-'A'+((n-x+1)*m+(m-y+1))/5<bst) return;
    for(int i=0;i<4;i++) {
        bool ok=1;
        for(int j=0;j<5;j++)
            if(now[x+dx[i][j]][y+dy[i][j]]!='.') {
                ok=0;
                break;
            }
        if(ok) {
            for(int j=0;j<5;j++)
                now[x+dx[i][j]][y+dy[i][j]]=ch;
            dfs(x,y+1,ch+1);
            for(int j=0;j<5;j++)
                now[x+dx[i][j]][y+dy[i][j]]='.';
        }
    }
    dfs(x,y+1,ch);
}
signed main() {
    cin>>n>>m;
    if(n<3||m<3) {
        cout<<0<<endl;
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++)
                cout<<'.';
            cout<<endl;
        }
        return 0;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            now[i][j]='.';
    bst=(n/3)*(m/3)-1;
    now[1][1]=now[1][2]=now[1][3]=now[2][2]=now[3][2]='A';
    dfs(3,4,'B');
    now[1][1]=now[1][2]=now[1][3]=now[2][2]=now[3][2]='.';
    now[1][1]=now[2][1]=now[3][1]=now[2][2]=now[2][3]='A';
    dfs(3,4,'B');
    cout<<bst<<endl;
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++)
            cout<<ans[i][j];
        cout<<endl;
    }
    return 0;
}

第二种代码 By SkyDec

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
74
75
#include<stdio.h>
#include<cstring>
using namespace std;
char ans[15][15];
char t[15][15];int res;
int Max[15];
char shape[5][5][5];
int n,m;
bool check(int x,int y,int type)
{
     for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
     if(shape[type][i][j]=='j')
     if(t[x+i][y+j]!='.')return 0;
     return 1;
}
void putshape(int x,int y,int type,int u)
{
     for(int i=0;i<3;i++)
     for(int j=0;j<3;j++)
     if(shape[type][i][j]=='j')
     t[x+i][y+j]=u;
}
void dfs(int x,int y,int now)
{
     if(x>n)
     {
            if(now-'A'>=res)
            {
                        for(int i=1;i<=n;i++)
                        for(int j=1;j<=m;j++)
                        ans[i][j]=t[i][j];
                        res=now-'A';
            }
            return;
            }
     int dx=x;int dy=y;dy++;
     if(dy>m)dy=1,dx++;
     if(now-'A'>Max[x]){Max[x]=now-'A';}
     if(now-'A'<Max[x]-3)return;
     for(int i=0;i<4;i++)
     if(check(x,y,i))
     {
                     putshape(x,y,i,now);
                     dfs(dx,dy,now+1);
                     putshape(x,y,i,'.');
                     }
     dfs(dx,dy,now);
}
void init()
{
     for(int i=1;i<=n;i++)
     for(int j=1;j<=m;j++)
     t[i][j]='.';
     shape[0][0][0]=shape[0][0][1]=shape[0][0][2]=shape[0][1][1]=shape[0][2][1]='j';

     shape[1][2][0]=shape[1][2][1]=shape[1][2][2]=shape[1][0][1]=shape[1][1][1]='j';

     shape[2][0][2]=shape[2][1][2]=shape[2][2][2]=shape[2][1][0]=shape[2][1][1]='j';

     shape[3][0][0]=shape[3][1][0]=shape[3][2][0]=shape[3][1][1]=shape[3][1][2]='j';
}
int main()
{
    scanf("%d%d",&n,&m);
    init();
    dfs(1,1,'A');
    printf("%d\n",res);
    for(int i=1;i<=n;i++)
    {
            for(int j=1;j<=m;j++)putchar(ans[i][j]);
            putchar('\n');
            }
    return 0;
}

DFS 可以使用也状压的记忆化来加速。当然也可以直接使用状压 DP。设 f[i][j][mask]f[i][j][mask] 表示当前考虑到 (i,j)(i,j)，前面 1818 格放的情况为 maskmask 的最优解。转移考虑放哪个角度（或不放）即可。

By rng_58

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>

using namespace std;

#define REP(i,n) for((i)=0;(i)<(int)(n);(i)++)
#define foreach(c,itr) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)

#define two(a,b,c,d) ((1<<(a))|(1<<(b))|(1<<(c))|(1<<(d)))

int dp[10][10][(1<<19)];
char ans[10][10];

int main(void){
    int X,Y,i,j,mask;

    cin >> X >> Y;

    int A = two(0,1,Y,2*Y);
    int B = two(Y-3,Y-2,Y-1,2*Y-1);
    int C = two(Y-1,2*Y-2,2*Y-1,2*Y);
    int D = two(Y-1,Y,Y+1,2*Y-1);

    int T = (1<<(2*Y+1));

    for(i=X-1;i>=0;i--) for(j=Y-1;j>=0;j--){
        int i2 = i, j2 = j+1;
        if(j2 == Y) {i2++; j2 = 0;}

        REP(mask,T){
            int mask2 = mask/2;
            dp[i][j][mask] = max(dp[i][j][mask], dp[i2][j2][mask2]);

            if(!(mask&1)){
                if(!(mask2&A) && i+2 < X && j+2 < Y) dp[i][j][mask] = max(dp[i][j][mask], dp[i2][j2][mask2|A] + 1);
                if(!(mask2&B) && i+2 < X && j-2 >= 0) dp[i][j][mask] = max(dp[i][j][mask], dp[i2][j2][mask2|B] + 1);
                if(!(mask2&C) && i+2 < X && j-1 >= 0 && j+1 < Y) dp[i][j][mask] = max(dp[i][j][mask], dp[i2][j2][mask2|C] + 1);
                if(!(mask2&D) && i+2 < X && j+2 < Y) dp[i][j][mask] = max(dp[i][j][mask], dp[i2][j2][mask2|D] + 1);
            }
        }
    }

    cout << dp[0][0][0] << endl;

    REP(i,X) REP(j,Y) ans[i][j] = '.';

    i = 0; j = 0; mask = 0;
    char ch = 'A';

    while(dp[i][j][mask] > 0){
        int i2 = i, j2 = j+1;
        if(j2 == Y) {i2++; j2 = 0;}

        int mask2 = mask/2;

        if(dp[i][j][mask] == dp[i2][j2][mask2]){
            i = i2; j = j2; mask = mask2;
            continue;
        }

        if(!(mask2&A) && i+2 < X && j+2 < Y && dp[i][j][mask] == dp[i2][j2][mask2|A] + 1){
            ans[i][j] = ans[i][j+1] = ans[i][j+2] = ans[i+1][j+1] = ans[i+2][j+1] = ch;
            i = i2; j = j2; mask = (mask2 | A); ch++;
            continue;
        }

        if(!(mask2&B) && i+2 < X && j-2 >= 0 && dp[i][j][mask] == dp[i2][j2][mask2|B] + 1){
            ans[i][j] = ans[i+1][j-2] = ans[i+1][j-1] = ans[i+1][j] = ans[i+2][j] = ch;
            i = i2; j = j2; mask = (mask2 | B); ch++;
            continue;
        }

        if(!(mask2&C) && i+2 < X && j-1 >= 0 && j+1 < Y && dp[i][j][mask] == dp[i2][j2][mask2|C] + 1){
            ans[i][j] = ans[i+1][j] = ans[i+2][j-1] = ans[i+2][j] = ans[i+2][j+1] = ch;
            i = i2; j = j2; mask = (mask2 | C); ch++;
            continue;
        }

        if(!(mask2&D) && i+2 < X && j+2 < Y && dp[i][j][mask] == dp[i2][j2][mask2|D] + 1){
            ans[i][j] = ans[i+1][j] = ans[i+1][j+1] = ans[i+1][j+2] = ans[i+2][j] = ch;
            i = i2; j = j2; mask = (mask2 | D); ch++;
            continue;
        }
    }

    REP(i,X){
        REP(j,Y) cout << ans[i][j];
        cout << endl;
    }

    return 0;
}