目录

291. 蒙德里安的梦想

91. 最短Hamilton路径

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

总体思路：

（1）核心：先放横着的，再放竖着的；如果横着的方块固定，竖着的方块自然也固定，得到总方案数为，只放横着的方块的合法方案数

（2）如何判断是否合法：判断每一列中放完横着的方块后，剩余的连续的空格是否为偶数，因为竖着的方块为两格方块，

状态表示的前提：表示第 i 列的状态可以用二进制表示，0表示该列未伸出到下一列，1表示伸出到了下一列，如 010 表示，该列第一行未伸到下一列，第二行伸出到了下一列，第三行未伸到下一列，如下图表示 010

闫氏DP分析法：

 解释两个条件：

（1）：第 i-1 列伸出的不能与第 i 列存在的重叠

（2）：空格长度必须是偶数，竖方块高度为2

时间复杂度分析：

共有 11 列，第 i-1 行有 2^11 种状态，第 i 列有2^11种状态，11*2^11*2^11 = 4000 0000 时间复杂度较危险，要预处理出来（1）连续偶数的状态（2）对于 i - 1的每种状态的匹配的状态的个数，如此可降低时间复杂度

最后要输出的结果为：f[m][0] 在前 m-1 列摆好，且第m列伸出为0的状态的方案，我们是从0 开始的所以，前m-1正好符合我们的需求

代码如下： 

#include 
#include 
#include 

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << N;

int n, m;
LL f[N][M];
vector state[M];
bool st[M];

int main()
{
    while(scanf("%d%d", &n, &m), n || m)
    {
        // 预处理每种状态的正确性（偶数连续）
        for(int i = 0; i < 1 << n; i ++ )
        {
            int cnt = 0;
            bool is_valid = true;
            for(int j = 0; j < n; j ++ )
            {
                if((i >> j) & 1)
                {
                    if(cnt & 1) 
                    {
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                }
                else cnt ++;
            }
            
            if(cnt & 1) is_valid = false;
            st[i] = is_valid;
        }
        
        //判断 每种状态可以匹配的下一种状态
        //（i-1行的所有状态可以匹配的第i行的状态）
        for(int i = 0; i < 1 << n; i ++ )
        {
            state[i].clear();
            for(int j = 0; j < 1 << n; j ++ )
            {
                if((i & j) == 0 && st[i|j]) state[i].push_back(j);
            }
        }
        
        // dp
        
        memset(f, 0, sizeof f);
        
        f[0][0] = 1;
        
        for(int i = 1; i <= m; i ++ )
        {
            for(int j = 0; j < 1 << n; j ++ )
            {
                for(auto k : state[j])
                {
                    f[i][j] += f[i-1][k];
                }
            }
        }
        
        cout << f[m][0] << endl;
        
    }
    
    return 0;
}

91. 最短Hamilton路径