题目链接【http://poj.org/problem?id=1038】
题意： 给出一个N*M大小的图，图中有K个坏点。N (1 <= N <= 150), M (1 <= M <= 10), K (0 <= K <= MN)；用2*3和3*2的木块去填这个图，问最多能放多少个木块。
题解：用一个三进制数表示某一行的状态，如果pos位置是0：表示该位置被占用了，pos位置是1：表示该位置没有被占用但是上一层的pos位置被占用了，pos位置是2：表示该位置和上一层的该位置否没有被占用。
用数组last[]和now[]表示上一层和本层的状态（用编码器和解码器实现）如果该位置为坏点那么now[pos]=0,否则now[pos]=min(2,last[pos]+1);用DFS实现，横着放，竖着放，或者不放，最后取最后一行每个状态下的值，取最大。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = ;
int dp[][maxn], cur;
int last[], now[];
int mp[][];
int T, Last, lim;
int n, m, k;
int en_code()//编码器
{
int ans = ;
for(int i = m - ; i >= ; i--) ans = ans * + now[i];
return ans;
}
void de_code(int x)//译码器
{
for(int i = ; i < m; i++)
{
last[i] = x % ;
x /= ;
}
}
void DFS(int pos, int val, int r)
{
if(pos == m)//本行已经处理完
{
int j = en_code();
dp[cur][j] = max(dp[cur][j], dp[cur ^ ][Last] + val);
return ;
}
if(mp[r][pos])//如果当前位置是坏点，直接跳过
{
now[pos] = ;
DFS(pos + , val, r);
return ;
}
now[pos] = min(, last[pos] + );//当前行pos点的状态
if(pos > && now[pos - ] == && now[pos - ] == && now[pos] == )//横着放
{
now[pos] = now[pos - ] = now[pos - ] = ;
DFS(pos + , val + , r);
now[pos] = now[pos - ] = now[pos - ] = ;//恢复到递归前的状态
}
if(pos && now[pos - ] == && last[pos - ] == && last[pos] == )//竖着放
{
now[pos] = now[pos - ] = ;
DFS(pos + , val + , r);
now[pos] = now[pos - ] = ;//恢复到递归前的状态
}
DFS(pos + , val, r);//不放
}
int main ()
{
scanf("%d", &T);
while(T--)
{
scanf("%d%d%d", &n, &m, &k);
lim = ;
cur = ;
for(int i = ; i <= m; i++) lim *= ;
memset(mp, , sizeof(mp));
for(int i = ; i <= k; i ++)
{
int x, y;
scanf("%d%d", &x, &y);
y--;
mp[x][y] = ;
}
memset(dp, -, sizeof(dp));
dp[][] = ;
for(int i = ; i <= n; i++)
{
cur ^= ;
memset(dp[cur], -, sizeof(dp[cur]));
for(int j = ; j <= lim - ; j++)
if(dp[cur ^ ][j] != -)
{
Last = j;
de_code(j);
DFS(, , i);
}
}
int ans = ;
for(int j = ; j <= lim - ; j++)
ans = max(ans, dp[cur][j]);
printf("%d\n", ans);
}
}