poj2411 Mondriaan's Dream （状压dp+多米诺骨牌问题）

这道题的解析这个博客写得很好

https://blog.csdn.net/shiwei408/article/details/8821853

大致意思就是我们可以只处理两行之间的关系，然后通过这两个关系推出所有行（有点像矩阵快速幂的思想）

几个要注意的地方

（1）第0行为全1

（2）发现自己的思维习惯还是先行在状态，我自己写得时候老是写反。

（3）path的个数可能有很多，不只是1<<n，可以输入极限数据然后输出路径的数目作为数组空间大小

（4）拿小的作列

（5）这道题是人为的设置一种方式，使得二进制与骨牌是一一对应的

如果是横放，就1 1 如果是竖放就 0 如果不放就是 1

11                        1                        0

然后这里的二进制操作非常的秀，要认真学习

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

typedef long long ll;

const int MAXN = 15;

ll dp[MAXN][2100];

int path[14000][2], p, n, m;

void dfs(int l, int now, int pre)

{

	if(l > m) return;

	if(l == m)

	{

		path[p][0] = pre;

		path[p++][1] = now;

		return;

	}

	dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);

	dfs(l + 1, (now << 1) | 1, pre << 1);

	dfs(l + 1, now << 1, (pre << 1) | 1);

}

int main()

{

	while(~scanf("%d%d", &n, &m) && n)

	{

		memset(dp, 0, sizeof(dp));

		if(m > n) swap(n, m);

		p = 0;

		dfs(0, 0, 0);

		dp[0][(1<<m)-1] = 1;

		_for(i, 1, n)

			REP(j, 0, p)

				dp[i][path[j][1]] += dp[i-1][path[j][0]];

		printf("%lld\n", dp[n][(1<<m)-1]);

	}

	return 0;

}