POJ 2411 Mondriaan's Dream

gate

一个很难想的题qaq

数据范围很小，可以状压DP。
考虑用二进制表示长方形状态：
横着的块两个格都为1，竖着的块上面为0，下面为1。

像这样，上面的格为1时，下面的可以随便放；上面的格为0时，下面必须为1。
用一个函数判断(i)行状态为(x)，(i-1)行状态为(y)是否合法：
设当前枚举到第(j)列，
若((i,j)=0)，则((i,j))向下放了一个竖块，必须有((i-1,j) ot=0)，下一个判断(j+1)；
若((i,j)=1, (i-1,j)=0)，则((i,j))向上放了一个竖块，下一个判断(j+1)；
若((i,j)=1, (i-1,j)=1)，则((i,j))向右放了一个横块，必须有((i-1,j+1) ot=0, (i,j+1) ot=0)，且(j+1le m)，下一个判断(j+2)；

全预处理会MLE，用的时候算会TLE
为了让状态尽量少，每次交换(n,m)，使(m)较小。

(code)

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define MogeKo qwq
using namespace std;

int n,m;
long long f[15][4500];
bool leg[4500][4500];

int read() {
	int x = 0,f = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-') f = -1;
		ch = getchar();
	}
	while('0' <= ch && ch <= '9') {
		x = x*10 + ch-'0';
		ch = getchar();
	}
	return x*f;
}

bool check(int y,int x) {
	int k = 0;
	while(k < m)
		if(x&(1<<k))
			if(y&(1<<k))
				if(x&(1<<(k+1)) && y&(1<<(k+1)) && k+1<m) k+=2;
				else return false;
			else k++;
		else {
			if((y&(1<<k))) k++;
			else return false;
		}
	return true;
}

int main() {
	while(1) {
		n = read(),m = read();
		if(!n && !m) break;
		if(m > n) swap(n,m);
		memset(leg,0,sizeof(leg));
		for(int i = 0; i < (1<<m); i++)
			for(int j = 0; j < (1<<m); j++)
				leg[i][j] = check(i,j);
		memset(f,0,sizeof(f));
		f[0][(1<<m)-1] = 1;
		for(int k = 1; k <= n; k++) {
			for(int i = 0; i < (1<<m); i++)
				for(int j = 0; j < (1<<m); j++)
					if(leg[i][j])
						f[k][i] += f[k-1][j];
		}
		printf("%lld
",f[n][(1<<m)-1]);
	}
	return 0;
}