AcWing 291. 蒙德里安的梦想(详细注释)
原题链接
中等
作者:
ros_275229
,
2024-03-29 19:44:08
,
所有人可见
,
阅读 3
(状态压缩dp) $O(m * 2^n)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 110 ;
bool st13N];
int f[13][2050] ;
int main(){
int n , m ;
while(cin >> n >> m ,m||n){
// 预处理 : 判断合并列的状态i是否合法
// 合并列1表示横放 , 0表示竖放
// 如果合并列存在连续奇数个0,为非法状态,反之合法
// 比如n=4的时候,合法状态有0(0000),3(0011),9(1001),12(11010),15(1111)
for(int i=0;i< 1<<n ;i++){ // 枚举到2^n-1,一共2^n个状态
st[i] = true ;
int cnt = 0 ; // 记录合并列中连续0的个数
for(int j=0;j<n;j++){//从低位到高位移
if(i>>j & 1){ // 如果是1
if(cnt&1){
st[i] = false ;
break ;// 记录i不合法
}
}else cnt ++ ;// 如果是0 , 记录0的个数
}
if(cnt & 1) st[i] = false ;//如0100,要判断高位0的情况
}
// 状态计算 :
memset(f , 0 , sizeof f) ;
f[0][0] = 1 ;// 第0列不横放是一种合法的方案
for(int i=1;i<=m;i++){// 阶段 : 枚举列
for(int j=0;j< 1<<n ;j++){ // 状态 : 枚举第i列的状态
for(int k=0;k< 1<<n;k++){ // 枚举第i-1列的状态
// 不出现重叠的1,不出现连续的奇数个0
if((j&k)==0 && st[j|k]){
f[i][j] += f[i-1][k] ;// 前一列兼容状态的方案数之和
}
}
}
}
cout << f[m][0] << endl ;// 第m列,不横放,即答案
}
}