AcWing 291. 蒙德里安的梦想(状态压缩dp典题,超全注释)
原题链接
中等
作者:
逸误
,
2024-04-07 14:50:17
,
所有人可见
,
阅读 6
//放好所有横放的方块,竖着放的可以装满,即为合法
//横放的合法方案数=总方案数
//状态表示:f[i][j]:前i-1列如何横放已经确定,伸到第i列的横条状态为j的方案数
//!状态划分:f[i][j]:可以划分为所有合法的f[i-1][k]之和(合法:k可以转移到j)
//合法性的两条判断:1、j伸出与k伸出完全无交集(j&k==0),2、第i列合法(j|k没有奇数个连续的0,导致竖条塞不满)
//注意需要保证前i-1列合法,但不用保证第i列就合法,这是放下一列的时候考虑的
//首先,预处理出所有单列状态中合法的部分,记录在st[1<<n]数组中
//然后三重循环,遍历每一列,再遍历i-1和i列的所有情况,如果两种状态兼容而且两种状态合法,就更新用于dp的f数组
#include <iostream>
#include <cstring>
using namespace std;
const int N = 15, M = (1<<11)+5;
int n,m;
long long f[N][M];
bool st[M];//存这次的n之下,状态m是否合法
int main()
{
while(1)
{
cin>>n>>m;
if(n==0&&m==0)
return 0;
//先预处理st数组,如果没有连续的奇数个0才合法
for(int i=0;i<1<<n;i++)//枚举状态
{
int cnt=0;
st[i]=true;
for(int j=0;j<n;j++)//枚举是第j位
{
if((i>>j)&1)//i状态的第j位是1
{
if(cnt&1)//前面是奇数个0
{
st[i]=false;
break;//i状态不合法
}
cnt=0;
}
else//第i位是0
cnt++;
}
//最后还是个边界条件,最下面有奇数个0不要忘记判定
if(cnt&1)
st[i]=false;
}
memset(f,0,sizeof f);
f[0][0]=1;
//现在st数组预处理好了,开始遍历状态
for(int i=1;i<=m;i++)//!!枚举列,放完后保证第i列合法性,不保证i+1列合法性!!
for(int j=0;j<1<<n;j++)//枚举左端放在第i列,伸到第i+1列的状态
for(int k=0;k<1<<n;k++)//枚举前面伸到第i列的状态
{
if((j&k)==0)//两种状态兼容(不能在同一个位置出现1,相当于前面刚伸出来现在又伸出来,明显是不合法的摆放方式)
if(st[j|k])//j|k合法,即在第i列(状态k)放完状态j后,第i-1列合法
f[i][j]+=f[i-1][k];
}
cout<<f[m][0]<<endl;
}
}