Mondriaan's Dream POJ - 2411 状压（有注释）

状压的方法参考博客：https://blog.csdn.net/hopeztm/article/details/7841917?utm_source=tuicool&utm_medium=referral

大佬的博客思想很好但是时间复杂度很高。

我利用大佬状压的思想写的DFS记忆化，跑了将近300ms。

///#include<bits/stdc++.h>
///#include<unordered_map>
///#include<unordered_set>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<bitset>
#include<set>
#include<stack>
#include<map>
#include<new>
#include<vector>
#define MT(a,b) memset(a,b,sizeof(a));
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double pai=acos(-1.0);
const double E=2.718281828459;
const int mod=1e9+7;
const int INF=0x3f3f3f3f;


ll dp[12][(1<<11)+10];
int n,m;

int judge(int i,int j)    ///j表示i的前一行
{
    ll k=0;
    while(k<m)
    {
        if(i>>k&1)      ///如果i的第k位是 1
        {
            if(j>>k&1)  ///如果j的第k位也是1，说明两个都是横放的，所以k+1都为1
            {
                if((k==m-1)||!((i>>(k+1))&1)||!((j>>(k+1))&1))
                    return 0;
                else    ///因为都是横放所以跳过下一位
                    k+=2;
            }
            else        ///如果i的第j位是 0,表示是合法的
                k++;
        }
        else            ///如果i的第k位是0，那么j的合法第k位应该为1
        {
            if(j>>k&1)
                k++;
            else
                return 0;
        }
    }
    return 1;
}

ll dfs(int dep,int pre)
{
    if (dep==(n+1))         ///递归结束，判断
        return (pre==(1<<m)-1)?1:0;
    if (dp[dep][pre]!=-1)   ///记忆化
        return dp[dep][pre];
    dp[dep][pre]=0;
    for (int cur=0; cur<(1<<m); cur++) ///枚举当前这一行的状态
    {
        if (judge(cur,pre))        ///判断这个状态和上一行是否兼容
            dp[dep][pre]+=dfs(dep+1,cur);
    }
    return dp[dep][pre];
}

int main()
{
    int i,j;
    while (scanf("%d%d",&n,&m)&&n+m)
    {
        if ((n*m)&1)    ///如果为奇数，肯定没有答案
        {
            printf("0\n");
            continue;
        }
        if (n<m)        ///因为列的复杂度为O(2^m),降低复杂度
            swap(n,m);
        memset(dp,-1,sizeof(dp));
        printf("%lld\n",dfs(1,(1<<m)-1));
    }
    return 0;
}