AcWing 291. 蒙德里安的梦想（状态压缩DP）

题目链接

https://www.acwing.com/problem/content/293/

思路

我们用一个n位二进制表示一列的情况，那么一列的情况有 2 n 2^n 2n种，我们枚举塞 1 × 2 1\times 2 1×2的方块数量，那么最后塞入 2 × 1 2 \times 1 2×1的方块的数量也是固定了的，我们定义 f [ i ] [ j ] f[i][j] f[i][j]表示已经将前 i − 1 i-1 i−1列摆好，且从第 i − 1 i−1 i−1列，伸出到第 i i i列的状态是 j j j的所有方案,我们枚举当前第 i i i列的情况时，我们应该是从 i − 1 i-1 i−1列的且列状态为满足条件的k状态转移过来即： f [ i ] [ j ] + = f [ i − 1 ] [ k ] f[i][j] += f[i-1][k] f[i][j]+=f[i−1][k]，对于每一种状态是否合法，我们可以提前预处理出来不用临时计算

更详细的思路请参见：https://www.acwing.com/solution/content/28088/

代码

#include
using namespace std;

#define ll long long
const int N = 12,M = (1