题目链接: http://hihocoder.com/problemset/problem/1048?sid=1171317
1.思路
状压DP经典题目,对于横着放的矩形,我们将两个格子都标记为1;对于竖着放的矩形,我们将(i-1,j) 标记为0, 将(i, j) 标记为1;
2.代码
/*********************************************************** FileName:hiho1048.cpp Author:zQ Email: zq216991@foxmail.com Create:2017-09-13 16:17:38 Descripttion:状压DP *************************************************************/ #define debug printf("%s: %d ", __FUNCTION__, __LINE__); // http://blog.csdn.net/hopeztm/article/details/7841917 #include <bits/stdc++.h> using namespace std; const int mod = 1e9+7; const int N = 1005; typedef long long ll; ll dp[N][N]; int n, m; // 预先处理第一行的状态 int testFirstLine(int s) { int i = 0; while(i < m) { if(s&(1<<i)) { if(i==m-1 || (s&(1<<(i+1)))==0) { return 0; } i += 2; } else { ++ i; } } return 1; } // 在位置(i, j) 如果我们选择横着贴砖,那么将(i, j), (i, j+1)都填写成1, 如果竖着贴砖,我们将(i,j)填写成0, 将(i+1, j)填写成1. bool ok(int a, int b) { int i = 0; while(i < m) { if((a&(1<<i)) == 0) { if((b&(1<<i)) == 0) { return false; } ++ i; } else { if((b&(1<<i)) ==0) { // 竖着铺 ++ i; } // 横着铺 else if(i != m-1 && (a&(1<<(i+1))) && (b&(1<<(i+1))) ) { i += 2; } else { return false; } } } return true; } int main() { cin >> n >> m; int x = (1<<m); for(int j = 0; j < x; ++ j) { dp[1][j] = testFirstLine(j); } for(int i = 2; i <= n; ++ i) { for(int j = 0; j < x; ++ j) { for(int k = 0; k < x; ++ k) { if(ok(j, k)) { dp[i][j] += dp[i-1][k]; dp[i][j] %= (ll)mod; } } } } printf("%lld ", dp[n][x-1]); return 0; }