蒙德里安的梦想

题目

题目链接

题解

动态规划。

对于每一种摆放的方式，如果我们将横向（1×2）的小矩形合理地摆放在棋盘中，那么纵向（2×1）的小矩形的摆放方式也就固定了。也就是说，我们只要确定了横向小矩形摆放的位置，只要将剩下位置填上纵向小矩形即可。因此，问题转化为了如何对横向小矩形进行合理地摆放。

定义状态表示：dp[i][j]表示棋盘的第i列的状态为j的方案数。 细细说来，规定横向小矩形的左侧小方格的位置能够代表整个小矩形的位置，举例说明一下，如果说在（1，2）放置了横向小矩形，则该矩形其实覆盖了（1，2）和（1，3）两个方格。 状态表示中的“状态j”是一个二进制表示，1表示该列的此位置（某一行）放置了横向小矩形，0表示未放置横向小矩形。（无论是将10010的最左侧的1理解为第一行，还是将最右侧的0理解为第一行都无所谓，对结果没有影响） 举例： 上面的状态对应的就是dp[1][(1001)]，而对于第二列，我们并没有放置小矩形，也就是说其实还没遍历到第二列。 上面的状态不仅有dp[1][(1001)]，还有dp[2][(0100)]。（不保证合理性，所以也就没法对dp进行赋值，只是单纯讲解dp数组的含义）

对于第i列的某一个状态j需要满足两个条件： ① 若第i-1列的状态为k，则由于不能出现横向小矩形覆盖的情况，所以如果第i-1列在第s行放置了小矩形，则第i列就不允许在第s行放置小矩形了，转换为代码：要保证k&j等于0。 ② 考虑到放完横向小矩形后还要放置纵向小矩形，所以必须保证每一列纵向连续的空格子数为偶数个（因为纵向小矩形的高度为2，连续空格子数必须为2的倍数）。对于这种情况，我们可以提前预处理，对于全部的情况j（0 ~ 1