AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
B1ackGod
,
2021-02-09 00:56:22
,
所有人可见
,
阅读 355
核心:动态规划,利用二进制表示状态,以此达到压缩状态,减少枚举状态的次数
- 我们只要枚举横着放的小长方形,那么竖着的长方形就是唯一的
也就是枚举横着放的小长方形等价于枚举所有方案
- 状态定义: f[i][j]表示第i列的前一列i-1列组成横着的小长方形(1*2的小方块放在i列和i-1列),第i列的每行是否有小方块用二进制的j表示。
- 属性:num,当前状态下的所有方案数(因此计算的时候要累加)
- 状态计算:上一状态用k表示,f[i][j]+=[i-1][k]
- 状态转移的条件:当前状态j和上一状态k(都是二进制表示)
5.1.j和k不冲突,也就是说放的方块不重叠,那么j&k==0
5.2.j和k放完之后,剩下的空格组合起来必须是偶数(因为2*1竖着放,必须是偶数个格子才能放),也就是必须是有 偶数个0。----j|k不存奇数0
第二点可以预处理得到,遍历每种状态,奇数0设置为false
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=12, M=1<<N;//M表示所有状态数,2的12次方
long long f[N][M];
bool st[M];
int n, m;
int main(){
while(cin>>n>>m,n||m){
//预处理不合法状态
for(int i=0; i<1<<n; i++){
st[i]=true;
int ctn = 0;//记录连续0的个数
for(int j=0;j<n;j++){
if(i>>j&1)
{
if(ctn&1){//如果是奇数
st[i]=false;
break;
}
}else ctn++;
}
if(ctn&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];
//最后的答案就是,第1~m-1列已经全部放好,第m列不放小方块
cout<<f[m][0]<<endl;
}
return 0;
}