AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
sailor
,
2021-02-19 14:55:03
,
所有人可见
,
阅读 282
// //基础课版本
// #include<iostream>
// #include<cstring>
// using namespace std;
// const int N=12, M=1<<N;
// typedef long long LL;
// int n,m;//n是行数,m是列数
// LL f[N][M];//最多有11列,没一列最多2^11个状态
// bool st[M];//储存每一列中,凸出来的二进制状态的十进制表示是否合法
// int main()
// {
// int n,m;
// while(cin>>n>>m, n||m)//只要有一个不是0就继续输入
// {
// memset(f,0,sizeof f);//每一轮要把状态表示清空
// //对于在每一列中可能出现的2^n个状态,
// // 先进行预处理,把一些不可行的状态筛出来
// //只对一列筛就行了,每一列都是一样的
// //当然,这里只是筛出来一列中不是连续个偶数个零的情况
// for(int i=0;i<1<<n;i++)
// {
// st[i]=true;//首先置为可行
// int cnt=0;//cnt记录当前连续0的个数
// //这列的二进制表示,对每一行的数进行筛选
// //从上到下,依次选
// for(int j=0;j<n;j++)
// if(i>>j & 1)//如果当前处理的这一位是1
// {
// //而前边有连续个奇数0,则当前状态直接不行
// if(cnt&1)
// {
// st[i]=false;
// // break; //为什么加了break之后还会变慢??
// }
// cnt=0;//置不置零无所谓
// }
// else cnt++;//如果当前处理的是0,直接++
// //对于当前处理的这个二进制数,最后再进行判断一次
// if(cnt&1) st[i]=false;
// }
// //状态初始化
// //-1列已经摆好,并且向0列伸出的方格数为0的情况有1种
// f[0][0]=1;
// for(int i=1;i<=m;i++)//枚举每一列
// for(int j=0;j<1<<n;j++) //枚举每一列的2^n中状态
// for(int k=0;k<1<<n;k++)//枚举上一列
// if((j&k)==0&&st[j|k])//j&k==0表示两列没有重叠
// // 已经知道st[]数组表示的是这一列没有连续奇数个0的情况,
// //我们要考虑的是第i-1列(第i-1列是这里的主体)中从第i-2列横插过来的,还要考虑自己这一列(i-1列)横插到第i列的
// //比如 第i-2列插过来的是k=10101,第i-1列插出去到第i列的是 j =01000,
// //那么合在第i-1列,到底有多少个1呢?自然想到的就是这两个操作共同的结果:两个状态或。 j | k = 01000 | 10101 = 11101
// //这个 j|k 就是当前 第i-1列的到底有几个1,即哪几行是横着放格子的
// f[i][j]+=f[i-1][k];//是合法状态的话,就加上
// //最后的答案,由于存的是0-m-1列,所以f[m][0]表示
// //前m-1列都已经放满,并且往第m列都没有伸出,即为0
// cout<<f[m][0]<<endl;
// }
// return 0;
// }
//提高课版本
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef long long LL;
const int N=12, M=1<<N;
int n,m;
LL f[N][M];
vector<int> state[M];//存放每个有效的状态
bool st[N];
int main()
{
while(cin>>n>>m, n||m)
{
//第一步预处理,把同一列中奇数
//个零连在一块的情况找出来
for(int i=0;i<1<<n;i++)
{
int cnt=0;
st[i]=true;
for(int j=0;j<n;j++)
if(i>>j &1)
{
if(cnt&1)
{
st[i]=false;
break;
}
cnt=0;
}
else cnt++;
if(cnt&1) st[i]=false;
}
//第二步预处理,排除所有的占据i和i+1列的格子
//和占据i-1和i列的格子重叠在一起的情况
//同时,把所有的合法情况加入到state中
for(int i=0;i<1<<n;i++)//枚举第i列
{
state[i].clear();//因为有很多轮输入,所有要先把上一轮样例的情况清空了
for(int j=0;j<1<<n; j++)//枚举第i-1列
if((i&j)==0&&st[i|j])//如果不重叠并且有偶数个0
//相邻的两列最多有2^11 * 2^11种情况
//我们只存储合法的情况
state[i].push_back(j);
}
//每一次都要把f数组初始化
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(auto k: state[j])//只遍历有效的状态即可
f[i][j]+=f[i-1][k];
cout<<f[m][0]<<endl;
}
return 0;
}