dp描述
状态集合描述
f[i][j]:前面i - 1列横放块已经合法摆好固定,且第i - 1列所摆横放块插入到第i列,使得第i列的状态为j 的所有摆法集合;
状态方程
f[i][j] += f[i - 1][k];(合法条件,i- 1列状态偶数零;状态j & 状态k == 0,即横放块不冲突)
合法条件代码注里释详细描述
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int N = 12, M = 1 << N;
typedef long long LL;
int n, m;
LL f[N][M];
vector<int> state[M];
bool st[M];
int main ()
{
while (cin >> n >> m, n || m)
{
//先处理每种状态j下的可行性,即连续零的个数为偶数;
for(int i = 0; i < 1 << n; i ++)
{
int cnt = 0;
bool is_valid = true;
for(int j = 0; j < n; j ++)
{
if(i >> j & 1)
{
if(cnt & 1)
{
is_valid = false;
break;
}
cnt = 0;
}
else cnt ++;
}
if(cnt & 1) is_valid = false;
st[i] = is_valid;
}
//优化:预处理所有状态所有合法前状态;
//合法:1、j & k == 0(i - 2列横放块插入 i - 1列的空隙中,即不重合)
// 2、偶数零, i - 1列和 i列的空隙为偶数,(因为是横向摆放,定义第i列固定,
// 此时i - 1列的状态由第i列和第i - 2列决定)
for(int j = 0; j < 1 << n; j ++)
{
state[j].clear();//数据一次多组, 故每次清空初始化;
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;
//回想f[i][j]的定义,此处为该列即第0列,
// 无上一列横放块插入,即只有这一竖直列,
// 无法横向只能竖向,故只有一种摆法
for(int i = 1; i <= m; i ++)
for(int j = 0; j < 1 << n; j ++)
for(auto s : state[j])
f[i][j] += f[i - 1][s];
cout << f[m][0] << endl;
}
}