poj 1308Bugs Integrated, Inc. [三进制状压]

题目链接【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 = 60050;
int dp[2][maxn], cur;
int last[15], now[15];
int mp[155][15];
int T, Last, lim;
int n, m, k;
int en_code()//编码器
{
    int ans = 0;
    for(int i = m - 1; i >= 0; i--) ans = ans * 3 + now[i];
    return ans;
}
void de_code(int x)//译码器
{
    for(int i = 0; i < m; i++)
    {
        last[i] = x % 3;
        x /= 3;
    }
}
void DFS(int pos, int val, int r)
{
    if(pos == m)//本行已经处理完
    {
        int j = en_code();
        dp[cur][j] = max(dp[cur][j], dp[cur ^ 1][Last] + val);
        return ;
    }
    if(mp[r][pos])//如果当前位置是坏点，直接跳过
    {
        now[pos] = 0;
        DFS(pos + 1, val, r);
        return ;
    }
    now[pos] = min(2, last[pos] + 1);//当前行pos点的状态
    if(pos > 1 && now[pos - 1] == 2 && now[pos - 2] == 2 && now[pos] == 2)//横着放
    {
        now[pos] = now[pos - 1] = now[pos - 2] = 0;
        DFS(pos + 1, val + 1, r);
        now[pos] = now[pos - 1] = now[pos - 2] = 2;//恢复到递归前的状态
    }
    if(pos && now[pos - 1] == 2 && last[pos - 1] == 2 && last[pos] == 2)//竖着放
    {
        now[pos] = now[pos - 1] = 0;
        DFS(pos + 1, val + 1, r);
        now[pos] = now[pos - 1] = 2;//恢复到递归前的状态
    }
    DFS(pos + 1, val, r);//不放
}
int main ()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &k);
        lim = 1;
        cur = 0;
        for(int i = 1; i <= m; i++) lim *= 3;
        memset(mp, 0, sizeof(mp));
        for(int i = 1; i <= k; i ++)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            y--;
            mp[x][y] = 1;
        }
        memset(dp, -1, sizeof(dp));
        dp[0][0] = 0;
        for(int i = 1; i <= n; i++)
        {
            cur ^= 1;
            memset(dp[cur], -1, sizeof(dp[cur]));
            for(int j = 0; j <= lim - 1; j++)
                if(dp[cur ^ 1][j] != -1)
                {
                    Last = j;
                    de_code(j);
                    DFS(0, 0, i);
                }
        }
        int ans = 0;
        for(int j = 0; j <= lim - 1; j++)
            ans = max(ans, dp[cur][j]);
        printf("%d
", ans);
    }
}

poj 1308Bugs Integrated, Inc. [三进制状压]

相关推荐