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;
}