蒙德里安的梦想
求把 N×M 的棋盘分割成若干个 1×2 的的长方形,有多少种方案。
状态压缩DP
解题思路
暴力求解:每个顶点都有3种方案:放两种;不放一种.最后判断是否恰好铺满.3^(n*m)*n*m
问题简化:我们可以先考虑横着方块摆放的方案,最后剩余空位判断是否能让竖着方块恰好填满.
如果方案合法那么剩余位置竖着方块摆放方案只有恰好填满一种,所以总的方案就是横着摆放方块的合法方案数.(排列组合
中的乘法原理 总方案数 = 横着摆放方案数 * 1).
那么接下来的问题是判断横着摆放后的状态是否能被竖着的小方块填满:判断每一列的连续空位是否
全为偶数即可.(竖着小方块不会伸向其他列,所以每一列独立判断)
状态压缩dp解决
状态定义:
我们按列从小到大摆放方块,称左边1*1小方块为起点,右边1*1方块为终点.行列下标从0开始.
下面方块表示横着的方块.
dp[i][s]
集合:0~i-1列已经摆放好(合法),且起点在i-1的方块集合为s.
属性:数目
举例:以N=2,M=3为例
dp[1][{0,1}]
集合:对应N=2,M=3的第一个图示
属性:1
s可以用二进制表示,第k位为1表示第k行为起点有方块.比如{0,1}可以表示为00...011
状态划分:
s表示以第i-1列作为起点的方块集合,我们考虑前一步也就是以第i-2列作为起点的方块集合.
i-2列的每一行都有两种选择,所以划分的子集和有2^n个.确定部分:第i-1列的起点集合;要求第i-2列
起点为s'的总数.为满足前i-2列方案合法,我们要求的是1~i-2列已经摆放好且i-2列起点集合为s'的数目.
根据集合定义为d[i-1][s'],所以
dp[i][s] = sum ( dp[i-1][s'] )
那么我们如何判断s'对于当前的s是合法的呢?
1.s与s'没有交集.(也就是不会重叠,因为s'的终点在i-1列)
2.s列合法.(s'终点与s起点剩余位置可以恰好放入竖着的小方块)
时间复杂度
状态数目 * 状态转移 = m2^n * 2^n
C++ 代码
#include<cstring>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
const int Max_N = 12, Max_M = 1<<Max_N;//0~m
int n, m;
bool st[Max_M]; //st[s]:某一列剩余空格为s的状态是否合法
vector<int> state[Max_M]; //st[s] = 对于第i-1列集合s合法的i-2列集合 (预处理 降低时间复杂度)
ll dp[Max_N][Max_M]; //状态
int main()
{
while( cin >> n >> m, n || m )
{
//预处理某一列状态是否合法
for( int s = 0; s < 1<<n; s++ )
{
int cnt = 0; //连续0(空格)的数目
bool is_valid = true; //s是否合法
for( int j = 0; j<n; j++ )
{
if( s >> j & 1 )
{//当前行不是空格 判断之前连续空格是否偶数
if( cnt&1 )
{//奇数 表面当前列状态不合法
is_valid = false;
break;
}
else cnt = 0; //偶数 合法 计数器置0
}
else cnt++; //当前行是空格 计数
}
if( cnt & 1 ) is_valid = false;
st[s] = is_valid;
}
//预处理对于d[i][s]合法的dp[i-1][s']
for( int s = 0; s < 1<<n; s++ )
{
state[s].clear();//多组数据 将之前数据清空
for( int s_ = 0; s_ < 1<<n; s_++ )
{
if( (s&s_)==0 && st[s|s_] )
{//没有交集 且第i-1列合法
state[s].push_back(s_);
}
}
}
//递推计算状态
memset( dp, 0, sizeof dp ); //多组数据 将之前数据清空
dp[0][0] = 1; //第i-1行不存在 所以第i-1行为起点的集合只有全0一种
for( int i = 1; i <= m; i++ )
{
for( int s = 0; s < 1<<n; s++ )
{
for( auto s_ : state[s] )
{
dp[i][s] += dp[i-1][s_];
}
}
}
cout << dp[m][0] << endl;//0~m-1列已经摆好 且第m列起点集合为空
}
return 0;
}