题目
题目链接: 蒙德里安的梦想
思路
状态压缩dp的经典例题
这个题的核心:先放横的,在放竖块。因为放完横块剩下的就填充成竖块即可。所以只需统计横块的合法方案数。
如何判断方案合法:放完横块之后,剩余空位置可以使用竖块填充铺满(按列来看就是每一列内空着的连续的位置为偶数个)。
DP->状态表示,化零为整的过程,集合表示
f[i][j]表示前i-1列已经摆好,第i-1列伸到第i列的情况为j的所有方案数
(j是一个二进制数,1表示伸过来了,0表示没有伸过来,是二进制数但用十进制存)
->状态划分,化整为零的过程,集合划分
就是将f[i][j]分割成若干个集合,最后求sum或min或max
分割依据一般都是以最后一步操作来分割,这里最后一步是f[i-1][k],即第i-2列伸到第i-1列
所以就将第i-1列的所有情况(i-2列伸到第i-1列)累加起来就是第i列的所有情况(i-1伸到第i列)
f[i-1][k]的合法方案的两个条件:
(1)i-2伸到i-1列的和i-1伸到i列的横块不能重合 -> j & k == 0
(2)对于第i-1列来说,连续的空位置必须是偶数个(只有这样才可以放下去竖块)
-> 第i-1列所有的连续空位置0位偶数个的合法方案:
首先我们要预处理出一个st[M]数组(bool),这个如果一个数j的二进制表示连续0位偶数个则st[j] = true
然后合法方案条件2就是需要满足st[j|k] == true 即可:
j | k => 第i-1列为1(位置不空)包括第i-2伸到的i-1列还有i-1列伸到i列的两种,所以把第i-1列所有
位置不为空的都填上1就是第i-1列的情况(状态压缩后所对应的十进制数),所以j|k
边界:f[0][0] = 1 :-1列不存在,所以伸到0列的情况状态为0,就这一种情况(计数dp一般f[0][0]都为1~)
最后要看的答案是f[m][0]:我们下标从0开始,所以本来填满范围为[0,m-1],而f[m][0]表示的是,第m-1列伸到第m列的状态为0,即没有伸到第m列,所以f[m][0]就是答案~~
代码
# include<iostream>
# include<algorithm>
# include<cstring>
# include<vector>
using namespace std ;
typedef long long LL ;
const int N = 12 ;
const int M = 1 << 11 ;
LL f[N][M] ;
vector<int> state[M] ; // 保存第i-1列每一种情况的合法方案的情况
bool st[M] ; // 保存某个情况是否是连续的偶数个0
int n,m ;
int main()
{
while(cin >> n >> m , n | m)
{
// 先预处理st
for(int i = 0 ; i < 1<<n ; i ++)
{
int cnt = 0;
bool is_valid = true ; // 该情况连续的0是否都为偶数
for(int j = 0 ;j < n ; j ++)
{
// 统计i的二进制表示中每一段连续的0是否为偶数
if(i >> j & 1) // 如果这一位为1 => 此时cnt就表示前一段连续的0的个数
{
if(cnt & 1) // 如果cnt为奇数
{
is_valid = false ;
break ;
}
cnt = 0 ; // 下一次cnt该统计下一段连续0的数量,这里需要置0
}
else cnt ++ ;
}
// 因为有可能最后一段0为考虑(1100100这种的0结尾情况)
if(cnt & 1) is_valid = false ;
st[i] = is_valid ;
}
// 预处理每一列的i-1列的合法方案
for(int j = 0 ; j < 1 << n ; j ++)
{
state[j].clear() ; // 每一组数据的state是不同的,要清空初始化
for(int k = 0 ; k < 1 << n ; k ++)
{
if((j & k) == 0 && st[j|k]) // 满足两个条件
state[j].push_back(k) ;
}
}
// 边界初始化
memset(f,0,sizeof f) ;
f[0][0] = 1 ; // -1列不存在, -1列伸到第0列的为0,所以只能是f[0][0]这一种情况
// 求f[i][j] ,下标从0开始,最后第m列应该为空,所以最后求f[m][0](0,m-1列都铺满的方案数)
for(int i = 1 ; i <= m ; i ++)
{
for(int j = 0 ; j < 1 << n ; j ++)
{
for(auto k : state[j])
{
f[i][j] += f[i-1][k] ;
}
}
}
cout << f[m][0] << endl ;
}
return 0 ;
}