题目描述

求把NM的棋盘分割成若干个12的的长方形，有多少种方案。

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

如下图所示：

2411_1.jpg

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

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

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

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

数据范围
1≤N,M≤11

样例

blablabla

算法1

这个题刚一接触太抽象了，本人觉得Y总的解释这样会好一点。

1. 首先状态表示。f[i][j]我觉得表示成横着的小方块放在第i列，j表示的是我可以将小方块放在第i列的第几行（注意这里的小方块的摆放形式是尾放在第i列，头放在i-1列上）。
   如果有n行，那么便有2^n中摆放状态。比如j=(10010)2,就意味着我想将将小方块放在第i列的第1、4两行，
   看看这种状态有几种方案。
   2.状态的更新。f[i][j]要想从f[i-1][k]中转移过来，就必须满足以下两个条件：
   （1）j这种摆放位置是否与前一列中的k这种摆放位置重叠，如果j&k==0，说明摆放位置不重叠。
   （2）j这种摆放是不是会使得前一列中出现了奇数的连续的空格，如果出现，不合理。

另外初始话f[0][0]可以理解为我想在第0列摆放小方块，但是小方块的尾端不能伸到第-1列上，
所以第0列不能摆放横着的小方块，所以j状态只能为0，什么也不放，这算是一种方案，所以f[0][0]=1;

时间复杂度：首先总共有11×2^11个状态，每次更新状态是时需要遍历2^11次k,所以总的时间复杂度为：11×2^11×2^11

C++ 代码

#include<iostream>
#include<cstring>

using namespace std;

const int N=13,M=1<<N;
long long  f[N][M];
bool st[M];//用来预处理那些状态（实际是横着的方块可以摆放的位置）是不合理的
int n,m;

int main()
{
    while(cin>>n>>m,n||m)
    {
        //预处理st[]数组
        for(int i=0;i<1<<n;i++)
        {
            st[i]=true;
            int cnt=0;
            for(int j=0;j<n;j++)
            {
                if(i>>j&1)
                {
                    if(cnt&1)
                    {
                        st[i]=false;
                        break;
                    }
                }
                else cnt++;
            }
            if(cnt&1)st[i]=false;
        }
        //初始化状态数组f
        memset(f,0,sizeof f);
        f[0][0]=1;//意味着我在第一列横的小方块不能放，状态为0，这是一种方案
        //状态更新
        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&&st[j|k])
                    {
                        f[i][j]+=f[i-1][k];
                    }
                }

            }
        }

        cout<<f[m][0]<<endl;

    }
    return 0;
}