给定一个m*n的方格子，要求用3*1的骨牌去覆盖，骨牌可以用横放或者竖放，问最终有多少种放置方式，将其铺满。
分析：由于最多30行，每行最多9列，所以可以按行来dp，设计每行的状态从而进行转移，考虑每个骨牌放置对下一行的影响，共有0,1,2，3种方式，0对应横放或者竖放时最下面那
个格子，此行对下一行没有影响，1,竖放时第1个，2竖放时第2个，这样进行转移。注意，第i行横放时要求上一行相应位置状态为0。
思路及代码都来自这里，其实不会做这题，看了才了解。
代码：
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<LL, int> MPS;
typedef pair<LL, LL> PII;
const int maxn = ;
LL dp[][maxn];
int st[];
int n, m;
void pre() {
st[] = ;
for(int i = ; i <= ; i++)
st[i] = st[i-]*;
}
int dig[];
void getDig(int x) {
int len = ;
memset(dig, , sizeof dig);
while(x) {
dig[len++] = x%;
x /= ;
}
}
void dfs(int cur, int state, int base, int prestate) {
if(cur == n) {
dp[base][state] += dp[base-][prestate];
return;
}
if(dig[cur] == ) {
if(cur+ < n && dig[cur+] == && dig[cur+] == ) {
dfs(cur+, state, base, prestate);
}
dfs(cur+, state+st[cur], base, prestate);
} else if(dig[cur] == ) {
dfs(cur+, state+*st[cur], base, prestate);
} else {
dfs(cur+, state, base, prestate);
}
}
int main() {
// in
pre();
while(scanf("%d%d", &n, &m), n || m) {
if(n*m%) {
puts("");
continue;
}
memset(dp, , sizeof dp);
dp[][] = ;
for(int i = ; i <= m; i++) {
for(int j = ; j < st[n]; j++) {
if(dp[i-][j]) {
getDig(j);
dfs(, , i, j);
}
}
}
printf("%lld\n", dp[m][]);
}
return ;
}
另一道类似的题目：HDU 4804 Campus Design
题意是：n*m的格子，用1*1和1*2的骨牌覆盖，但是有一些格子不需要覆盖，而且最终要求所用的1*1的骨牌个数num满足：c <= num <= d.
解法类似，每个格子被覆盖的情况有两种，0和1，即1*2格子竖放的第一个，1*2格子竖放第2个或者1*1格子，或者不需要覆盖，这样按行进行转移就行了。
代码：
#include <cstdio>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <vector>
#define pb push_back
#define mp make_pair
#define esp 1e-14
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
#define sz(x) ((int)((x).size()))
#define pf(x) ((x)*(x))
#define pb push_back
#define in freopen("solve_in.txt", "r", stdin);
#define bug(x) printf("Line : %u >>>>>>\n", (x));
#define inf 0x0f0f0f0f
using namespace std;
typedef long long LL;
typedef map<LL, int> MPS;
typedef pair<LL, LL> PII; const int M = (int)1e9 + ;
const int maxn = ;
const int maxm = ; LL dp[maxn][][maxm];
int n, m, c, d;
char maze[maxn][];
int dig[]; void getDig(int x) {
memset(dig, , sizeof dig);
int len = ;
while(x) {
dig[len++] = x&;
x >>= ;
}
}
bool check(char *s, int x) {
for(int i = ; s[i]; i++) {
if((x&) && s[i] == '') return false;
x >>= ;
}
return true;
}
void dfs(int pre, int num, int st, int cur, int state, int cnt) {
if(cnt > d) return;
if(cur == m) {
dp[pre+][cnt][state] = (dp[pre+][cnt][state]+dp[pre][num][st])%M;
return;
}
if(maze[pre+][cur] == '') {
dfs(pre, num, st, cur+, state, cnt);
} else if(dig[cur] == ) {
if(cur+ < m && dig[cur+] == && maze[pre+][cur+] == '')
dfs(pre, num, st, cur+, state, cnt);
if(pre+ < n && maze[pre+][cur] == '')
dfs(pre, num, st, cur+, state+(<<cur), cnt);
dfs(pre, num, st, cur+, state, cnt+);
} else {
dfs(pre, num, st, cur+, state, cnt);
}
}
int main() { while(scanf("%d%d%d%d", &n, &m, &c, &d) == ) {
memset(dp, , sizeof dp);
for(int i = ; i <= n; i++)
scanf("%s", maze[i]);
dp[][][] = ;
for(int i = ; i < n; i++) {
int j;
if(i == ) {
j = ;
getDig(j);
int x = ;
if(dp[i][x][j])
dfs(i, x, j, , , x);
} else {
for(int j = ; j < (<<m); j++) {
if(check(maze[i], j) == false) continue;
getDig(j);
for(int x = ; x <= d; x++) if(dp[i][x][j])
dfs(i, x, j, , , x);
}
}
}
LL ans = ;
for(int i = c; i <= d; i++)
ans = (ans + dp[n][i][])%M;
printf("%lld\n", ans);
}
return ;
}