Mondriaan 的梦（HG 2018.4.15 试题1 T3）

## 题目部分 ### 【题目描述】 正方形和长方形让荷兰著名画家皮特·蒙德里安着迷了。一天晚上，在他画完了他的“厕所系列” （因为蒙德里安的画纸都已经画满了正方形和长方形，他不得不用厕所纸来作画）之后，他又幻想着 用 1×2（高×宽）的矩形画满厕所纸。 因为厕所纸有限，他想知道有多少种方式可以画满一张厕所纸。 比如当厕所纸如下大小时，用 1×2 的矩形，可以画出以下图形：  请你帮他计算一下，以免他的梦想变成噩梦。 ### 【输入格式】 只有一行 2 个整数，分别为高 h 和宽 w，（1<=h,w<=11) ### 【输出格式】 画法总数。假设厕所纸是有方向的，即对称的画法算不同的画法。若无法画满，则输出 0。 ### 【输入样例】 2 4 ### 【输出样例】 5 ------------ ------------ ------------ ## 题解部分 一道状压DP，用f[i][j]表示前i-1行已经填完，第i行状态为j的方案数。 j是表示状态的2进制数，如10010表示第一个位置和第四个位置已经被填了。 对于该行某个位置j： 如果前一行该位置为0,那么该位置可以竖放 即 0->1 如果前一行连续两个位置为0,那么这两个连续位置可以横放 即00->00 如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0 ，即1-> 0 ------------ 若当前状态为s,对s 有下列操作： 1. 判断第i位是否为0 -> (s & 1 << i) == 0，意思是将1左移i位与s进行与运算后，看结果是否为0. 2. 将第i位置变为1 -> s | 1 << i，意思是将1左移动i位与s进行或运算. 3. 将第i位置变为0 -> s & !(1 << i)，意思是s与第i位为0，其余位为1的数进行与运算。 ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; long long f[15][1<<15]; void dfs(int i,int j,int s,int p) { if(p==m) { f[i][j]+=f[i-1][s]; return; } if((1<<p)&j) dfs(i,j,s,p+1); else { dfs(i,j,(s|(1<<p)),p+1); if(p+2<=m && !(j&(1<<(p+1)))) dfs(i,j,s,p+2); } } int main() { scanf("%d%d",&n,&m); if(n%2 && m%2)//特判，都为奇数无法填满，不加也可以 { cout<<0; return 0; } f[1][0]=1; for(int i=1;i<=n+1;i++) for(int j=0;j<(1<<m);j++) dfs(i,j,0,0); cout<<f[n+1][0]; return 0; } ``` ------------ 关于为什么两个都是奇数就填不满： 1.总方格数为奇数，而两个两个填总数必为偶数，矛盾 2.牛逼的染色法，将图进行奇偶染色如下图 ------------  ------------ 然后 ------------  ------------ 这样子，图被奇偶染色。然后你发现，怎么填，都会覆盖一个黑和一个白像这样 ------------  ------------ 所以覆盖的黑的总数必定和白的总数相等，但是当都是奇数时黑和白的总数不相等，故不成立。 还有很多神奇的数学染色方法，有兴趣的自行百度啦