AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
跟着灿哥学切菜
,
2021-01-22 15:32:48
,
所有人可见
,
阅读 259
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
long long f[N][M];
bool st[M];
int main()
{
while (cin >> n >> m, n || m)
{
//枚举所有的状态是否不存在连续个0, 此时就是将1左移n位
for (int i = 0; i < 1 << n; i ++ )
{
//cnt表示的是当前的这一段连续的0的个数
int cnt = 0;
//假设其实成立的
st[i] = true;
for (int j = 0; j < n; j ++ )
//如果当前这一位是1, 说明上一段已经截止了, 此时需要来判断上一列中的0是否是奇数个
//如果此时是奇数个, 此时表示第i个状态是不合法的, 里面存在有连续奇数个0。
if (i >> j & 1)
{
if (cnt & 1) st[i] = false;
cnt = 0;
}
else cnt ++ ;
//如果最后一段中0的个数是true, 此时将最后一段的状态设置成为false;
if (cnt & 1) st[i] = false;
}
//下面是动态规划的过程
memset(f, 0, sizeof f);
//在最开始的时候,也就是表示如果此时整个题目中只要一列这种状态的话, 此时只要一种放的方法
//就是将所有的小的矩形都是竖着放(如果可以)
f[0][0] = 1;
for (int i = 1; i <= m; i ++ )
for (int j = 0; j < 1 << n; j ++ )
for (int k = 0; k < 1 << n; k ++ )
if ((j & k) == 0 && st[j | k])
f[i][j] += f[i - 1][k];
cout << f[m][0] << endl;
}
return 0;
}