题目大意：要在n * m的网格上面铺满1 * 2或者 2 ＊ 1的砖块，问有多少种铺放的方式
解题思路：刚开始用了3进制表示每行的状态,0表示的是2 * 1的砖块的一部分，1表示的是1 ＊ 2的砖块的上部分，2表示的是1 ＊ 2的砖块的下部分，然后像poj－1185炮兵阵地 那题一样去解决就好了，结果发现状态太多了，会TLE，只得放弃了
后面参考了下别人的代码，可以将其转换成二进制表示形式的，0代表没该位置没被铺到，1代表该位置有被铺到
因为有1 * 2的这种影响两行的砖头存在，所以要判断两个状态能否吻合，只有吻合了才可以
分类讨论
1.如果第i行的第j列是1
A.如果第i－1行的第j列也是1，那么这里铺的砖就不可能是1＊2这种类型的砖(影响2行的砖)，也就是他们两个铺的都是2*1的砖，那就要判断其相邻的那个是不是也是1了，如果不是，就表示两种状态不吻合了
B.如果第i－1行的第j列是0，那么表示第i行第j列的砖是1 ＊ 2的砖，上部分将第i－1行的第j列给铺了
2.如果第i行的第j列是0
A.如果第i－1行的第j列也是0，那么就出现空缺了，不符合
B.如果第i－1行的第j列是1，就表示第i行需要第i＋1行铺1 ＊2的砖来填补了
可参考大神的题解这里写链接内容
A的代码
#include
#include
#include
using namespace std; #define maxn 15 #define maxs (1 << 12) long long ans[maxn][maxn]; long long dp[maxn][maxs]; int h, m; bool ok(int s) { for(int i = m - 1; i >= 0; i--) { if(s & (1 << i)) { if(i == 0) return false; if(!(s & (1 << (i - 1)))) return false; i--; } } return true; } bool judge(int s, int ss) { for(int i = (m - 1); i >= 0; i--) { if(!(ss & (1 << i)) && !(s & (1 << i))) return false; if((s & (1 << i))) { if(ss & (1 << i)) { if(i == 0) return false; if(!(s & (1 << (i - 1))) || !(ss & (1 << (i - 1)))) return false; i--; } } } return true; } void solve() { int t; if(h < m) { t = h; h = m; m = t; } memset(dp, 0, sizeof(dp)); for(int i = 0; i < (1 << m); i++) if(ok(i)) dp[1][i] = 1; for(int r = 2; r <= h; r++) for(int s = 0; s < (1 << m); s++) for(int ss = 0; ss < (1 << m); ss++) if(judge(s, ss)) dp[r][s] += dp[r-1][ss]; printf(%lld , ans[h][m] = ans[m][h] = dp[h][(1 << m) - 1]); } int main() { memset(ans, -1, sizeof(ans)); while(scanf(%d%d, &h, &m) != EOF && h + m) { if(ans[h][m] != -1) { printf(%lld , ans[h][m]); continue; } if((h * m) % 2 == 1) { ans[h][m] = ans[m][h] = 0; printf(0 ); continue; } solve(); } return 0; }
三进制超时的代码
#include
#include
#include
#include
using namespace std; #define maxn 270000 int state[maxn]; int dp[12][maxn]; int w, h, cnt; int mod[13]; void init() { memset(dp, 0, sizeof(dp)); cnt = 0; bool flag1, flag2; for(int i = 0; i < mod[w]; i++) { flag1 = flag2 = false; for(int j = w - 1; j >= 0; j--) { if((i % mod[j + 1] - i % mod[j]) / mod[j] == 0) { if(j == 0) { flag1 = true; break; }else { if((i % mod[j] - i % mod[j - 1]) / mod[j - 1] != 0) { flag1 = true; break; } } j--; } } if(!flag1) { for(int j = w - 1; j >= 0; j--) { if((i % mod[j + 1] - i % mod[j]) / mod[j] == 2) { flag2 = true; break; } } } if(!flag1) state[cnt++] = i; if(!flag1 && !flag2) dp[0][i] = 1; } } int solve() { for(int r = 1; r < h; r++) for(int i = 0; i < cnt; i++) for(int j = 0; j < cnt; j++) { bool flag = false; for(int k = w - 1; k >= 0; k--) { if(((state[j] % mod[k + 1] - state[j] % mod[k] ) / mod[k] == 1) && ( (state[i] % mod[k + 1] - state[i] % mod[k] ) / mod[k] != 2)) { flag = true; break; } if(((state[i] % mod[k + 1] - state[i] % mod[k] ) / mod[k] == 2) && ( (state[j] % mod[k + 1] - state[j] % mod[k] ) / mod[k] != 1)) { flag = true; break; } } if(!flag) { dp[r][state[i]] += dp[r-1][state[j]]; } } int ans = 0; for(int i = 0; i < cnt; i++) { bool flag = false; for(int j = w - 1; j >= 0; j--) if((state[i] % mod[j + 1] - state[i] % mod[j]) / mod[j] == 1) { flag = true; break; } if(!flag) { ans += dp[h - 1][state[i]]; } } return ans; } void begin() { mod[0] = 1; for(int i = 1; i < 13; i++) mod[i] = mod[i - 1] * 3; } int main() { begin(); while(scanf(%d%d, &h, &w) != EOF && h + w) { if((h * w) % 2 == 1) printf(0 ); else { init(); printf(%d , solve()); } } return 0; }
?