题意 : 给定矩形的长宽, 要求用1*2的矩形有多少种方法摆法能密铺掉原来的矩形

>> face <<

Strategy:状压DP, i是一个表示二进制的十进制数,'1’标记每个竖着放置的矩形的上半部分 其他情况标记为0

状态: dp[i][r] -> 密铺到第r行, 状态i所对应的摆法

目标: dp[0][n] -> 最后一行全0

边界: dp[0][0] = 1;

合法判断: 当上行的状态’j’,下行的状态’i’, j & i == 0(不存在上面一个1下面也是1), i | j 连续的0必须是偶数(两个竖着的矩形之间只能夹着偶数个0)

转移方程:

$$dp[i][r]=dp[j][r-1]$$

attention: 可以预处理出每个合法的状态,

双倍经验: 注意枚举的边界

#include <bits/stdc++.h> // #include<bits/extc++.h> // #define oo INT_MAX #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define _rev(i, a, b) for (int i = (a); i >= (b); --i) #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rof(i, a, b) for (int i = (a); i > (b); --i) #define ll long long #define all(x) x.begin(), x.end() #define db double #define eps 0.00001 #define met(a, b) memset(a, b, sizeof(a)) #define lowbit(x) x &(-x) #define cost first #define what_is(x) cerr << #x << " is " << x << endl; #define val second #define oo INT_MAX #define pi acos(-1.0) using namespace std; const int maxn = 1 << 12; ll dp[maxn][12]; int n, m; bool valid[maxn]; int main() { while (cin >> n >> m && n) { memset(dp, 0, sizeof(dp)), memset(valid, 0, sizeof(valid)); bool zeros = 0, is_odd = 0; _for(i, 0, (1 << m)) { //筛出所有合法状态 bool zeros = 0, is_odd = 0; _for(j, 0, m) { if ((i >> j) & 1) { //如果是1 is_odd |= zeros; if (is_odd) break; } else { zeros ^= 1; } } valid[i] =( is_odd | zeros ? 0:1); } dp[0][0] = 1; _rep(r, 1, n){ _for(i, 0, (1 << m)){//当前行的状态 _for(j, 0, (1 << m)){//上一行的状态 if(!valid[j | i])continue; if((j & i) != 0)continue; dp[i][r] += dp[j][r - 1]; } } } cout << dp[0][n] << endl; } }