poj1038 Bugs Integrated, Inc.

英文题面

Bugs Integrated, Inc. is a major manufacturer of advanced memory chips. They are launching production of a new six terabyte Q-RAM chip. Each chip consists of six unit squares arranged in a form of a 23 rectangle. The way Q-RAM chips are made is such that one takes a rectangular plate of silicon divided into NM unit squares. Then all squares are tested carefully and the bad ones are marked with a black marker.

Finally, the plate of silicon is cut into memory chips. Each chip consists of 23 (or 32) unit squares. Of course, no chip can contain any bad (marked) squares. It might not be possible to cut the plate so that every good unit square is a part of some memory chip. The corporation wants to waste as little good squares as possible. Therefore they would like to know how to cut the plate to make the maximum number of chips possible.
Task
You are given the dimensions of several silicon plates and a list of all bad unit squares for each plate. Your task is to write a program that computes for each plate the maximum number of chips that can be cut out of the plate.
Input
The first line of the input file consists of a single integer D (1 <= D <= 5), denoting the number of silicon plates. D blocks follow, each describing one silicon plate. The first line of each block contains three integers N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN) separated by single spaces. N is the length of the plate, M is its height and K is the number of bad squares in the plate. The following K lines contain a list of bad squares. Each line consists of two integers x and y (1 <= x <= N, 1 <= y <= M) ?coordinates of one bad square (the upper left square has coordinates [1, 1], the bottom right is [N,M]).
Output
For each plate in the input file output a single line containing the maximum number of memory chips that can be cut out of the plate.
Sample Input
2
6 6 5
1 4
4 6
2 2
3 6
6 4
6 5 4
3 3
6 1
6 2
6 4
Sample Output
3
4

题目大意

  一个n*m的网格图,有一些障碍点,用2*3或3*2的骨牌覆盖,求最多能放多少张骨牌.

提示

  m特别小,想到状压.

代码

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
106

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 160;
int T,n,m,num,vis[maxn][maxn],p[12],q[12],now,last,f[2][177150],ans,temp1;

int (int *y)
{
int res = 0;
for (int i = 1; i <= m; i++)
res = res * 3 + y[i];
return res;
}

void jie(int x)
{
for (int i = m; i >= 1; i--)
{
p[i] = x % 3;
x /= 3;
}
}

void dfs(int dep,int cnt)
{
if (dep > m)
return;
int temp2 = zhuan(q);
f[now][temp2] = max(f[now][temp2],f[last][temp1] + cnt);
if (dep + 1 <= m && p[dep] == 0 && p[dep + 1] == 0 && q[dep] == 0 && q[dep + 1] == 0)
{
q[dep] = q[dep + 1] = 2;
int temp = zhuan(q);
f[now][temp] = max(f[now][temp],f[last][temp1] + cnt + 1);
dfs(dep + 2,cnt + 1);
q[dep] = q[dep + 1] = 0;
}
if (dep + 2 <= m && q[dep] == 0 && q[dep + 1] == 0 && q[dep + 2] == 0)
{
q[dep] = q[dep + 1] = q[dep + 2] = 2;
int temp = zhuan(q);
f[now][temp] = max(f[now][temp],f[last][temp1] + cnt + 1);
dfs(dep + 3,cnt + 1);
q[dep] = q[dep + 1] = q[dep + 2] = 0;
}
}

int main()
{
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d",&n,&m,&num);
memset(vis,0,sizeof(vis));
for (int i = 1; i <= num; i++)
{
int x,y;
scanf("%d%d",&x,&y);
vis[x][y] = 1;
}
memset(p,0,sizeof(p));
memset(q,0,sizeof(q));
for (int i = 1; i <= m; i++)
if (vis[1][i])
p[i] = 2;
now = 1,last = 0;
int temp = zhuan(p);
memset(f,-1,sizeof(f));
f[0][temp] = 0;
for (int i = 2; i <= n; i++)
{
memset(f[now],-1,sizeof(f[now]));
for (int j = 0; j < 177147; j++)
{
if (f[last][j] != -1)
{
jie(j);
for (int k = 1; k <= m; k++)
{
if (vis[i][k])
q[k] = 2;
else
{
q[k] = p[k] - 1;
if (q[k] < 0)
q[k] = 0;
}
}
temp1 = zhuan(p);
dfs(1,0);
}
}
swap(now,last);
}
ans = 0;
for (int i = 0; i < 177147; i++)
ans = max(ans,f[last][i]);
printf("%dn",ans);
}

return 0;
}

分析

  很容易想到状态压缩. 关键就是如何表示出状态. 仅仅只用0,1表示状态是不够的,需要用3进制表示状态. 若第i位为0,则表示当前行的第i位和它上面的那个位置没有被占,若为1,则表示上面的位置被占,当前位置没有被占,若为2,则表示当前位置被占了. 为什么要这么表示状态?因为骨牌的数量与骨牌能不能放有关,若在第i行第j列放,则考虑骨牌能否以(i,j)为左下角. 这样必须要记录上面两行的信息. 因为考虑的是骨牌的下边界,所以从第i行转移到第i+1行时,2 —> 1, 1 —> 0,所有的骨牌都往上挪一格. 利用上一行的信息可以知道上上一行的信息.
  这样的状态数高达$3^10$,若枚举上一行的状态和当前行的状态,时间上承受不了. 注意到有障碍格子的存在,会有很多无效状态. 这些无效状态中,一部分是当前行的状态与障碍格子冲突产生的,一部分是当前行的状态与上一行的状态冲突产生的. 利用刷表法处理掉无效状态,而不是枚举. 因为枚举相当于复杂度没变. 考虑从当前状态向下一层状态扩展,利用dfs搜出放骨牌的所有决策,然后更新.

总结

  处理无效状态可以利用刷表法,而不是枚举状态+判不合法. 后一种方法只能应用于对于每一行的状态而言,限制条件都是一样的情况.
  填表法可以用dfs转移(转移太复杂太多).