题目描述
将高为H，宽为W的棋盘分割成若干个宽和高分别为1和2的长方形，有多少种方案。
输入描述
第一行为H，W。
输出描述
输出方案数。
测试用例
输入
2 2
输出
2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 1000005
ll h, w;
ll dp[12][1 << 12];
bool check(ll s) {
ll cnt = 0;
for (ll i = 0; i < w; ++i)
if (s & (1 << i)) {
if (cnt % 2 != 0)
return false;
cnt = 0;
} else
cnt++;
return cnt % 2 == 0;
}
int main() {
cin >> h >> w;
dp[0][0] = 1;//第0行全部横着
for (ll i = 1; i <= h; i++) {
for (ll s1 = 0; s1 < (1 << w); s1++) {
for (ll s2 = 0; s2 < (1 << w); s2++) {
if ((s1 & s2) != 0) continue;
if(!check(s1 | s2)) continue;
dp[i][s1]+=dp[i-1][s2];
}
}
}
cout << dp[h][0];//最后一行必须全部横着
return 0;
}