Mondriaan's Dream 题解

用二维数组dp，第一维表示状态，第二维表示当前行。最后输出的是最后一行全部都横着放的状态。用1表示竖着放，0表示横着放，注释详细。。。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll dp[1<<12][12]; 
int h,w;
bool judge(int x)//判断连续的0是不是偶数个
{
    int ww=w;
    int cnt=0;
    while(ww--)
    {
        if(x&1) {
            if(cnt&1) return false;
            cnt=0;
        }
        else cnt++;
        x>>=1;
    }
    if(cnt&1) return false;
    return true;
}
int main()
{
    while(scanf("%d%d",&h,&w)!=EOF)
    {
        if(h==0&&w==0) break;
        int len=(1<<w)-1;
        dp[0][0]=1;//边界
        for(int r=1;r<=h;r++)
        {
            for(int j=0;j<=len;j++)//枚举这一行
            {
                if(j&&(r==h)) break;//加这行提高效率
                dp[j][r]=0;
                for(int i=0;i<=len;i++)//枚举上一行
                {
                    if(i&&(r==1)) break;//加这行提高效率
                    if(i&j) continue;//如果两行都放竖的，不可能
                    if(!judge(i|j)) continue;//如果这样，无法用1x2的填充
                    dp[j][r]+=dp[i][r-1];//累加方案
                }
            }
        }
        printf("%lld\n",dp[0][h]);
    }
}