AcWing 291. 蒙德里安的梦想
题目描述
求把NM的棋盘分割成若干个12的的长方形,有多少种方案。
例如当N=2,M=4时,共有5种方案。当N=2,M=3时,共有3种方案。
输入格式
输入包含多组测试用例。
每组测试用例占一行,包含两个整数N和M。
当输入用例N=0,M=0时,表示输入终止,且该用例无需处理。
输出格式
每个测试用例输出一个结果,每个结果占一行。
数据范围
1≤N,M≤11
题解
这道题揭发为动态规划中的状态压缩,初次接触时也是整的一脸懵逼
题目分析
摆放方块的时候,先放横着的,再放竖着的。总方案数等于只放横着的小方块的合法方案数。
如何判断,当前方案数是否合法? 所有剩余位置能否填充满竖着的小方块。可以按列来看,每一列内部所有连续的空着的小方块需要是偶数个。
这是一道动态规划的题目,并且是一道 状态压缩的dp:用一个N位的二进制数,每一位表示一个物品,0/1表示不同的状态。因此可以用0→2N−1(N二进制对应的十进制数)0→2N−1(N二进制对应的十进制数)中的所有数来枚举全部的状态。
状态表示
首先这里强调,我的代码虽然和别的大佬的代码一样,
但从理解方面不同,视频中小方块伸出的方向是向右的,
而我在接下来的题解中,小方块伸出的方向是向左的,f[i][j]表示第i列状态为j,即f[i][0]涵盖了发f[i-1]的所有状态
没理解可以从下面的代码中慢慢理解,切记不要囫囵吞枣;
状态转移
f[i][j]是f[i-1]中能与j状态伸出的重合时合法的情况的总和;
所以发f[i][j]=f[i-1][x1]+f[i-1][x2]+f[i-1][x3]+······
代码如下
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int N=12,M=1<<N;
long long f[N][M];
bool st[M]; //记录某种状态是否有连续个奇数零;
vector<vector<int>> state(M); //记录某种状态相匹配的状态
int main()
{
int n, m;
while(cin >> n >> m, n != 0 && m != 0)
{
//预处理 1;
//首先找到存在连续的奇数零的状态,cnt表示连续奇数的数量;
for(int i=0;i< 1<<n;i++)
{
int cnt=0;
st[i]=true;
//因为用二进制储存状态,所以查看状态时就要用位运算逆推回去;
for(int j=0;j<n;j++)
{
//如果遇到横向方块,则检查上方是否为连续奇数个0;
if(i>>j &1)
{
//如果为奇数个0,则将st记为false,表示此状态不合法;
if(cnt&1) st[i]=false;
//初始化cnt,重新记录;
cnt=0;
}
//如果不是横向方块,则连续0的数量+1;
else cnt++;
}
//因为最后一段可能是0,所以还需要检查最后一段;
if(cnt&1) st[i]=false;
}
//预处理 2;
//此步是将第i-2列和i-1列伸出去的有冲突的排除;
for(int i=0;i< 1<<n;i++)
{
//因为是多组数据,所以每次要清空上次残留的操作;
state[i].clear();
//对每个状态开始遍历;
for(int j=0;j< 1<<n;j++)
{
//两个状态需要同时满足以下两点:
//1.两个状态不发生冲突,即i-1列伸出的不会与i-2列重合;
//2.i-1列伸出的和i-2列的合并后不会出现连续奇数个0;
if((i&j)==0 && (st[i|j]==true))
{
//记录下每个状态可以匹配的状态;
state[i].push_back(j);
}
}
}
//清除上个测试点残留的数据;
memset(f,0,sizeof(f));
//预处理 3;
//dp开始,首先这里再次强调,我的代码虽然和别的大佬的代码一样,
//但从理解方面不同,f[i][0]表示第i列状态为0,即f[i][0]涵盖了发f[i-1]的所有状态;
//初始状态,对于 f[0][0]来说只有竖着一种状态,而其他状态越界不合法;
f[0][0]=1;
//开始遍历每一列;
for(int i=1;i<=m;i++)
{
//遍历当前列(第i列)所有状态j;
for(int j=0;j< 1<<n;j++)
{
//遍历第i-1列的状态k,如果“真正”可行,就转移;
for(auto k:state[j])
{
f[i][j]+=f[i-1][k];
}
}
}
//最后结果是第m列(实际上是m+1列)的0状态,因为0状态涵盖了m-1列(实际上是m列)的所有情况;
cout<<f[m][0]<<endl;
}
return 0;
}