【每日一题】打卡 31

 

 原题链接：291. 蒙德里安的梦想 - AcWing题库

 算法：状压dp

  主要思想就是利用二进制上的1和0来分别表示在一个位置，放和不放1*2的横着的长方形，例如若一列有四个格子十进制表示为4，放和不放可以表示成0~(1<<4)-1,也就是二进制上的0~1111，它一定能遍历到所有摆放情况。然后我们需要判断摆放是否合法，需要判断0的个数不能为奇数个，也一列上就是不能有奇数个空格，因为我们枚举的是横着的摆放，枚举完横着的，剩下的空格就要放竖着的，若空格长度为奇数，竖着的长方形会塞不满或者塞不下。最后枚举各个列的时候，需要判断前一个列是否有伸出的长方格于该列的长方格重叠，并且判断前一个列伸出的长方格与该列长方格的并集是否合法。

#include
#define int long long
using namespace std;
const int N=12;
int f[12][1<
int st[1<
signed main() {
	int n,m;
	while(cin>>n>>m&&n&&m) {
		memset(f,0,sizeof f);
		for(int i=0; i<1<
			st[i]=1;
			int cnt=0;
			for(int j=0; j
				if(i>>j&1) {
					if(cnt&1) {
						st[i]=0;
						break;
					}
				} else  cnt++;
			}
			if(cnt&1)st[i]=0;
		}
		f[0][0]=1;
		for(int i=1; i<=m; i++)
			for(int j=0; j<1<
				for(int k=0; k<1<
					if(!(j&k)&&st[k|j])f[i][j]+=f[i-1][k];
				}
		cout<0]<
	}
}