AcWing 291. 蒙德里安的梦想
原题链接
中等
作者:
cys02
,
2023-03-22 20:26:28
,
所有人可见
,
阅读 116
解题思路:
- $dp[i.j]$ 代表的是第 $i$ 列,状态为 $j$ 时,对应的摆放方式的个数;另一种表述方式: $dp[i, j]$ 表示第 $i - 1$ 列伸出的状态是 $j$ 的方案数。
- 考虑这一行有上一列延伸出来,为1;否则为0,以一串二进制的数字代表状态,则 $[0,2^{n-1}]$ 可以表示所有的状态
- 这一列的状态为 $j$ ,上一列的状态为 $k$ ,考虑在什么情况下状态可以转移:
- 横着放的木块中间的空行必须是偶数,否则无法放入竖着的木块,所以 $[j|k]$ ( $j$ 和 $k$ 取或)的值,不能有奇数个连续的0。( $j$ 的某一行为1,则代表该列有木块从 $k$ 中延伸过来, $k$ 中的这一列有木块,k的某一行为1,代表 $k$ 的上一列延伸到 $k$ ,所以 $[j|k]$ 代表的是 $k$ 中的木块情况),可以设置一个
bool
类型的数组,预先处理所有 $[j|k]$ 的情况,并判断哪些可用;
- $j$ & $k$ 必须为0,因为 $j$ 的某一行为1,代表有木块从 $k$ 中延伸过来, $k$ 的这一行是这个木块开始的位置,一定不会有木块延伸自上一列。
C++代码:
#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int N=12,M=1<<N;
bool jud[M];//若该状态没有连续的奇数个数的0,jud为true
LL dp[N][M];//表示第i列,状态为j时,对应的摆放方式的个数
void solve(){
while(true){
int n,m;
cin>>n>>m;
if(n==0&&m==0)break;
for(int i=0;i<(1<<n);i++){ //枚举所有状态,预处理jud数组
jud[i]=true;
int cnt=0; //cnt记录的是连续0的个数
int num=i;
for(int j=0;j<n;j++){ //i表示一个状态,遍历i的每一位,查看是否有连续的奇数个的0
if((i>>j)%2==0){
cnt++;
}
else{
if(cnt%2==1){
jud[i]=false;
break;
}
cnt=0;
}
}
}
cout<<jud[0]<<" "<<jud[1]<<endl;
memset(dp,0,sizeof(dp));
dp[0][0]=1; //第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&&jud[j|k]){ //满足要求,可以进行状态转移
dp[i][j]+=dp[i-1][k];
}
}
}
}
cout<<dp[m][0]<<endl;//0是第一列,m-1是最后一列,m列没有任何木块延伸自m-1列的情况.
//其实就是第m-1列摆满的情况
}
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T=1;
// cin>>T;
while(T--){
solve();
}
return 0;
}