AcWing 291.蒙德里安的梦想

题目：蒙德里安的梦想##

链接:(蒙德里安的梦想)[https://www.acwing.com/problem/content/293/]

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

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

分析：

1.当把所有横着的长方形放置好后，那么竖着的长方形的放置方法是唯一的

2.f[i, j]表示放置第i列时，第i列的状态是j的所有方案，j表示从第i - 1列伸出方块到第i列的状态

3.竖着的空着方块是用来放置1 * 2的长方形的，因此需要连续偶数个空方块，我们可以预处理出来是否能放置

4.如何正确地转移？首先不能产生冲突，f[i - 1, k]表示放置第i - 1列时，k是从i - 2列伸出来到i - 1列的方块

所以为了避免产生冲突，要放置长度为2的长方形，k & j必须为0，某一列的某一行只能放置一个方块

5.j | k，假设j的某一行有一个方块，那么k这里会从0填充到1，然后k剩余的方格里有没有连续的偶数个方块

#include <cstring>

#include <cstring>

#include <iostream>

using namespace std;

const int n = 12;

const int m = 1 << 12;//第二维状态最大有2^12种可能

typedef long long ll;

bool st[m];//state，预处理好的状态

ll f[n][m];

int main()

{

	int n, m;

	while (scanf("%d%d", &n, &m), n || m) {

		//预先处理好状态，在DP过程中直接判断

		for (int i = 0; i < 1 << n; ++i) {

			st[i] = true;//先设置好每个状态为1

			int cnt = 0;//统计连续0的个数

			for (int j = 0; j < n; ++j) {//判断每一位是否为0

				if (i >> j & 1) {//判断之前已经累计好的0个数为奇数

					if (cnt & 1)

						st[i] = false;//为奇数，设置为false

					cnt = 0;//重新累计0的个数

				}

				else {

					++cnt;//没碰到1，就累计0的个数

				}

			}

			if (cnt & 1)

				st[i] = false;//如果最后的是连续的0，没有碰到1，就需要再判断一下

		}

		memset(f, 0, sizeof f);

		f[0][0] = 1;

		for (int i = 1; i <= m; ++i) {//m + 1列，多计算m + 1列

			for (int j = 0; j < 1 << n; ++j) {//i列的第二维状态

				for (int k = 0; k < 1 << n; ++k) {//i - 1列的第二维状态

					if ((j & k) == 0 && st[j | k]) {

						f[i][j] += f[i - 1][k];

					}

				}

			}

		}

		printf("%lld\n", f[m][0]);

	}

	return 0;

}

巴特西

AcWing 291.蒙德里安的梦想

题目：蒙德里安的梦想##

最新文章

热门文章