AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
少年
,
2020-09-07 20:27:18
,
所有人可见
,
阅读 369
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int N=12,M=1<<N;
long long f[N][M];
int n,m;
bool st[M];
vector<int> fair[M];
//f[i][j]表示前i-1列已经摆好(不会再加横放小矩形),且伸出到第i列(第二个小方块在第i列)的形式为j的所有方案数
//j用二进制来表示第i列哪个格子被占(该位为1),没有被占为0
//例如第i列第一行第二行最后一行被占(这里假设共五行)则j的二进制表示为11001
//这里我们只枚举横着放的小矩形即可(只要合理,剩下的部分就可以直接填充竖着放的矩形)
//如何判断合理与否?所有剩余位置,能否填满竖着的小矩形,按列来看,就是每列是否有偶数个相邻小方块
//f[i][j]从上一步转化
//f[i-1][k]如何能够转化为f[i][j]
//首先小矩形不能同时伸到第i-1列和第i列(小矩形的最后一个方块的位置固定)--> (k&j)=0
//其次i-1列的空余部分应满足有连续偶数小方块(填放竖着的小矩形) , 第i-1列填满的部分为 k | j(用二进制去对应位置想),判断这个数是否是由连续偶数0和一些1组成
int main()
{
while(cin>>n>>m, n||m)
{
for(int i=0;i< 1<<n;i++) //判断这个范围的数是否满足由连续偶数0和一些1组成
{
int cnt=0;
bool flag=true;
for(int j=0;j<n;j++)
{
if(i>>j & 1) //这位是1
{
if(cnt & 1) //cnt 为奇数
{
flag=false;
break;
}
}
else cnt++;
}
if(cnt & 1) flag=false; //数字j的最后一部分可能只是一些连续0,要判断是奇数还是偶数
st[i]=flag;
}
//因为是多次计算,所以数组有重复使用,使用前要清空一下
for(int i=0;i< 1<<n;i++) //判断一列对应的合理前一列的二进制表示
{
fair[i].clear();
for(int j=0;j< 1<<n ; j++)
if((i&j)==0 && st[i|j]) //满足从第i-1列延申到第i列的条件
fair[i].push_back(j); //对应这个数所有的合理前一列方案
}
memset(f,0,sizeof f);
//空时初始化为1
f[0][0]=1;
//列数从1枚举
for(int i=1;i<=m;i++)
for(int j=0;j< 1<<n;j++)
for(auto t:fair[j])
f[i][j]+=f[i-1][t]; //从小到大累加
//我们的答案是要填好最后一列没伸展出来的方案数
cout<<f[m][0]<<endl;
}
return 0;
}
//f[0][0]=1这部分还不能很好的解释,已经理解的大佬分享一下,感谢