题目描述
求把 N×M 的棋盘分割成若干个 1×2 的长方形,有多少种方案。
例如当 N=2,M=4 时,共有 5 种方案。当 N=2,M=3 时,共有 3 种方案。
朴素版思路
1、使用状态压缩,将每一列的$ n $个格子都当成一个二进制数,用$0$和$1$表示其状态,则共有$2 ^ n$种状态。
2、对于一个合法的状态,要求其二进制表示中不能有连续奇数个$0$。
3、$f[i][j]$ 表示已经摆好$i$列,且第i列状态为$j$的方案数。
4、枚举第$i - 1$列的合法状态。
合法条件
- 不能出现重叠的1
- 不能出现连续奇数个1
C++ 代码
#include<iostream>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
bool st[M];
int main() {
while (cin >> n >> m, n || m) {
for (int i = 0; i < 1 << n; i ++ ) {
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j ++ ) {
if ((i >> j) & 1) {
if (cnt & 1) { // 判断是否有连续奇数个1
st[i] = false;
break;
}
} else cnt ++ ;
}
if (cnt & 1) st[i] = false;
}
memset(f, 0, sizeof f);
f[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 && st[j | k]) // 判断状态是否合法
f[i][j] += f[i - 1][k];
}
cout << f[m][0] << endl;
}
return 0;
}
优化版
使用$vector$存储每个状态所对应的合法序列,减少遍历时间
C++代码
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
typedef long long LL;
using namespace std;
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
bool st[M];
vector<int> state[M];
int main() {
while (cin >> n >> m, n || m) {
for (int i = 0; i < 1 << n; i ++ ) {
int cnt = 0;
st[i] = true;
for (int j = 0; j < n; j ++ ) {
if ((i >> j) & 1) {
if (cnt & 1) {
st[i] = false;
break;
}
} else cnt ++ ;
}
if (cnt & 1) st[i] = false;
}
// 优先存储每个状态所对应的合法状态
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;
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;
}