考点

状态压缩DP

题目描述

291.蒙德里安的梦想

求把 N×M 的棋盘分割成若干个 1×2 的的长方形，有多少种方案。

例如当 N=2，M=4 时，共有 5 种方案。当 N=2，M=3 时，共有 3 种方案。

输入格式
输入包含多组测试用例。

每组测试用例占一行，包含两个整数 N 和 M。

当输入用例 N=0，M=0 时，表示输入终止，且该用例无需处理。

输出格式
每个测试用例输出一个结果，每个结果占一行。

数据范围
1≤N,M≤11

样例

输入样例：
1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0


输出样例：
1
0
1
2
3
5
144
51205

C++ 代码

# include <iostream>
# include <cstring>
using namespace std;
const int N = 15 , M = 1 << N;

long long f[N][M]; // f[i][j], i为当前列，i - 1列伸到了第i列的二进制表示的值为j。
int choose[M];

int n,m;

int main()
{
    while(~scanf("%d %d",&n,&m) && (n || m))
    {
        memset(f,0,sizeof f);  //由于每一次的循环，f内已经有值了，所以每一次循环都要重新初始化为0.

        for(int i = 0 ; i < 1 << n ; i++)  //判断0 ~ 1 << n - 1的二进制表示下是否有连续的奇数个0
        {
            choose[i] = 1;
            int res = 0;  //连续0的个数
            for(int k = 0 ; k < n ; k++)
            {
                if(i >> k & 1)
                {
                    if(res & 1) 
                    {
                        //res 为奇数
                        choose[i] = 0;
                        res = 0;
                        break;
                    }
                    else
                    {
                        res = 0;
                    }
                }
                else
                {
                    res++;
                }
            }

            //有可能最后连续多个0，也需要判断最后连续的0是否为奇数
            if(res & 1)
            {
                choose[i] = 0;
            }
        }
        f[0][0] = 1;

        for(int i = 1 ; i <= m ; i++)
        {
            for(int j = 0 ; j < 1 << n ; j++)
            {
                for(int k = 0 ; k < 1 << n ; k++)
                {
                    if((j & k) == 0 && choose[j | k])
                    {
                        f[i][j] += f[i - 1][k]; 
                    }
                }
            }
        }
        printf("%lld\n",f[m][0]);
    }
    return 0;
}