【POJ 2411】Mondriaan’s Dream

题目传送门：http://poj.org/problem?id=2411

轮廓线dp

#include<iostream>
#include<cstdio>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = (1<<12)+9;

int n,m;
LL f[2][MAXN];

int main(){
	while (scanf("%d%d",&n,&m) && (n || m)) {
		int now=1, pre=0, MX=1<<n;
		memset(f[now],0,sizeof(f[now]));
		f[now][0] = 1;
		
		for (int j=1;j<=m;j++) {
			for (int i=1;i<=n;i++) {
				swap(now, pre);
				memset(f[now],0,sizeof(f[now]));
				for (int k=0;k<MX;k++) if (f[pre][k]) {
					f[now][k^(1<<i-1)] += f[pre][k];
					if (i > 1 && k&(1<<i-2) && !(k&(1<<i-1)))
						f[now][k^(1<<i-2)] += f[pre][k];
				}
			}
		}
		printf("%lld\n",f[now][0]);
 	}
	return 0;
}