Mondriaan's Dream（状压dp）

解决问题的关键是简化问题，利用推出的条件进行分析往往比基于原题笼统的分析更加通畅。

分析:

横的用11表示，竖的用法01表示。
合法的状态应该是相邻两行的或是全1，与的话不存在连续的1的个数是奇数的。可以确定的是第0行和第n行一定都是1
初始化的时候认为第0行全是1，也即dp[0][(1 << m) - 1] = 1
**

代码:

**

#include <bits/stdc++.h>
using namespace std;
long long dp[12][2050];

bool check(long long x)
{
	long long cnt = 0;
	while(x)
	{
		if(x & 1) cnt++;
		else
		{
			if(cnt & 1) return false;
			cnt = 0;
		}
		x >>= 1;
	}
	if(cnt & 1) return false;
	return true;
}


signed main()
{
	long long n, m;
	while(cin >> n >> m && n && m)
	{
		memset(dp, 0, sizeof(dp));
		dp[0][(1 << m) - 1] = 1;
		for(long long i = 0; i < n; i++)
			for(long long j = 0; j < (1 << m); j++)
				if(dp[i][j] > 0)
				{
					for(long long k = 0; k < (1 << m); k++)
						if((j | k) == (1 << m) - 1 && check(j & k))
							dp[i + 1][k] += dp[i][j];
				}
		cout << dp[n][(1 << m) - 1] << endl;
	}
}