【题解】蒙德里安的梦想

  • Post author:
  • Post category:其他




前言

很经典的状态压缩dp,第一次提交超时,不知道改了改什么地方,再提交居然A了,很离谱…



题目:

蒙德里安的梦想



题意:

求把 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



思路:

  • 我们会发现,对于任意一种情况,只要它的横向方块确定了,那么竖向的方块只有一种可能,所以我们只需要枚举横向方块的情况就可以。总方案数:等于只放横向方块的合法方案数。
  • 怎么判断是否合法?其实就是看剩余的位置是否能用竖向方块填满,如果可以就说明是合法的。可以每一列来看,如果有连续的奇数个方格没有放,那么说明不合法。
  • 另外在dp时需要保证上一列和下一列不能存在 “冲突” ,也即不能让某列的一个格子被两个方块都放过。
  • 用M来表示每列最多有多少种情况,M是对应的二进制数。因为我们用二进制的形式表示某种情况,所以M的取值范围是[000…0, 111…1]。
  • 这里的某个 “情况” 指的是从上一列凸出来的方块摆放 “情况” 。
  • 因为我们要额外向后询问一列,所以N要设置为12。



代码:

#include<iostream>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>

using namespace std;

const int N = 12, M = 1 << N;
#define ll long long 

ll f[N][M]; //对于f[i][(10010)B]表示第i列的第一行和第四行有方块凸出来,存的是这种情况下的方案数。
bool st[M];//记录第i种情况是否符合条件: 也即不存在连续奇数个零
int n, m;

int main()
{
	while (cin >> n >> m, n || m)
	{
		memset(f, 0, sizeof f);

		//对于每一列进行预处理,遍历所有情况将含有奇数个连续零的可能剔除。
		for (int i = 0; i < 1 << n; ++i)
		{
			st[i] = true;
			int cnt = 0;//记录连续零的个数
			for (int j = 0; j < n; ++j)
			{
				//注意是询问i的二进制数中有多少个0,所以应该是右移
				if (i >> j & 1)
				{
					if (cnt & 1)st[i] = false;
					cnt = 0;
				}
				else cnt++;
			}
			//如果最后没有遇到零那么不会在循环里判断,所以要特判
			if (cnt & 1)st[i] = false;
		}

		//因为第1列不存在前面的列,所以不可能有方块凸出来,于是只有(000...0)B这一种情况
		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)
				{
					//st[j | k]表示的是两种情况合并后的情况
					//注意,比较运算符的优先级高于按位运算符
					if ((j & k) == 0 && st[j | k])
					{
						f[i][j] += f[i - 1][k];
					}
				}
			}
		}
		//我们是从0开始枚举的,所以只需要枚举到m-1行合法的情况即可。那么对应的就是第m行没有任何方块凸出来。
		cout << f[m][0] << endl;
	}

	return 0;
}



版权声明:本文为jhgjhg225原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。