power oj 2480 放积木[二进制状压DP]

题目链接【https://www.oj.swust.edu.cn/problem/show/2480】

题意：中文题目。

题解：二进制状态转移+坏点判断。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long LL;

const int maxn =  << ;

LL dp[][maxn];

int mp[];

char s[];

int n, m;

int cur;

void DFS(int r, int pos, int nu, int z, int cnt)

{

    if(pos == m)

    {

        dp[cur][nu] = max(dp[cur][nu], dp[cur ^ ][z] + cnt);

        return ;

    }

    if(mp[r] & ( << pos)) //坏点

    {

        DFS(r, pos + , nu, z, cnt);

        return ;

    }

    if(!(z & ( << pos)) && !(mp[r - ] & ( << pos)))

        DFS(r, pos + , nu | ( << pos), z, cnt + );

    else

    {

        if( pos && !(nu & ( << (pos - ))) && !(mp[r] & ( << (pos - ))) )

            DFS(r, pos + , nu | ( << pos) | ( << (pos - )), z, cnt + );

        DFS(r, pos + , nu, z, cnt);

    }

}

int main ()

{

    while(~scanf("%d%d", &n, &m))

    {

        memset(mp, , sizeof(mp));

        for(int i = ; i <= n; i++)

        {

            scanf("%s", s);

            for(int j = ; j < m; j++)

                if(s[j] == '*') mp[i] |=  << j;

        }

        cur = ;

        memset(dp[], -, sizeof(dp[]));

        int mask = ( << m) - ;

        dp[][mask] = ;

        for(int i = ; i <= n; i++)

        {

            cur ^= ;

            memset(dp[cur], -, sizeof(dp[cur]));

            for(int j = ; j <= mask; j++)

                if(dp[cur ^ ][j] >= )

                    DFS(i, , , j, );

        }

        LL ans = ;

        for(int i = ; i <= mask; i++)

            ans = max(ans, dp[cur][i]);

        printf("%lld\n", ans);

    }

    return ;

}