POJ 1038 Bugs Integrated, Inc.

三进制状压 DP。

用 0/1/2 表示一个格子下方没有格子 / 1 个格子 / 2 个格子被覆盖，转移时枚举上一行状态，在单行内搜索生成所有合法的下一行状态转移，可过（

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 150;
const int M = 10;
const int S = 59049;
int T,n,m,k,full;
int pw[M + 5];
int a[N + 5][M + 5];
int f[N + 5][S + 5],ans;
int s,pre;
void trans(int i,int j,int v)
{
    if(j > m)
    {
        f[i][s] = max(f[i][s],v);
        return ;
    }
    if(j < m && i + 1 < n && !a[i][j] && !a[i][j + 1] && !(pre / pw[j - 1] % 3) && !(pre / pw[j] % 3))
        s += pw[j - 1] + pw[j] << 1,
        trans(i,j + 2,v + 1),
        s -= pw[j - 1] + pw[j] << 1;
    if(j + 1 < m && i < n && !a[i][j] && !a[i][j + 1] && !a[i][j + 2] && !(pre / pw[j - 1] % 3) && !(pre / pw[j] % 3) && !(pre / pw[j + 1] % 3))
        s += pw[j - 1] + pw[j] + pw[j + 1],
        trans(i,j + 3,v + 1),
        s -= pw[j - 1] + pw[j] + pw[j + 1];
    trans(i,j + 1,v);
}
int main()
{
    pw[0] = 1;
    for(register int i = 1;i <= M;++i)
        pw[i] = pw[i - 1] * 3;
    scanf("%d",&T);
    for(;T;--T)
    {
        memset(a,0,sizeof a),memset(f,-1,sizeof f),ans = 0;
        scanf("%d%d%d",&n,&m,&k),full = pw[m] - 1;
        for(int x,y;k;--k)
            scanf("%d%d",&x,&y),a[x][y] = 1;
        f[0][0] = 0;
        for(register int i = 1;i <= n;++i)
            for(register int j = 0,flag;j <= full;++j)
                if(~f[i - 1][j])
                {
                    pre = s = j,flag = 0;
                    for(register int l = 1;l <= m;++l)
                        if(s / pw[l - 1] % 3)
                        {
                            if(a[i][l])
                            {
                                flag = 1;
                                break;
                            }
                            s -= pw[l - 1];
                        }
                    !flag && (trans(i,1,f[i - 1][j]),1);
                }
        for(register int i = 0;i <= full;++i)
            ans = max(ans,f[n][i]);
        printf("%d\n",ans);
    }
}