Mondriaan's Dream POJ

Mondriaan's Dream POJ"/>

Mondriaan's Dream POJ

一、内容

题意：给定n，m， 将1x2的小方格放入其中，求有多少种方法。

二、思路

• F【i】【j】代表对于i列 该列横向放小方块的状态为j， 里面存放的是方案数。j代表二进制状态1代表该行放了小方块
• 我们先设i行的状态为j,i-1行的状态为k。
• 由于我们枚举了所有横着放小方块的状态，那么剩下的位置只能竖着放小方块，所以我们要求连续0的位置必须是偶数，因为竖着放小方块占2行，所以必须空出2个位置出来。所以 j | k 这个状态下连续0必须是偶数。
• 还有就是与i-1列的状态不能冲突，因为若i-1列的某行已经放了一个小方块，那么i列的这行就不能放了，所以 (j & k) == 0。

三、代码

#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 12;
ll f[N][1 << N];
bool st[1 << N];
int n, m;
int main() {while (scanf("%d%d", &n, &m), n){memset(f, 0, sizeof(f));//每次统计下状态中奇数0的情况 连续0为奇就是falsefor (int i = 0; i < 1 << n; i++) {int cnt = 0;st[i] = true; //代表初始化是偶数个0 for (int j = 0; j < n; j++) {if (i & (1 << j)) {//代表遇到一个1if (cnt & 1) break;cnt = 0; } else {cnt++;}}if (cnt & 1) st[i] = false;}f[0][0] = 1; //初始状态 //枚举i列状态 和i-1列状态  列是0~m-1 for (int i = 1; i <= m; i++) {for (int j = 0; j < 1 << n; j++) {for (int k = 0; k < 1 << n; k++) {//前一个状态表示不冲突  后一个表示连续0为偶数if ((j & k) == 0 && st[j | k]) {f[i][j] += f[i - 1][k];}}} }	//最后输出答案0~m-1 列已经拍好 那么m列就是000...00这个状态printf("%lld\n", f[m][0]); }return 0;
}