首页 > 代码库 > ZOJ 2563 Long Dominoes（状压DP）
ZOJ 2563 Long Dominoes（状压DP）
给定一个m*n的方格子，要求用3*1的骨牌去覆盖，骨牌可以用横放或者竖放，问最终有多少种放置方式，将其铺满。
分析：由于最多30行，每行最多9列，所以可以按行来dp，设计每行的状态从而进行转移，考虑每个骨牌放置对下一行的影响，共有0,1,2，3种方式，0对应横放或者竖放时最下面那
个格子，此行对下一行没有影响，1,竖放时第1个，2竖放时第2个，这样进行转移。注意，第i行横放时要求上一行相应位置状态为0。
思路及代码都来自这里，其实不会做这题，看了才了解。
代码：
1 #include <bits/stdc++.h> 2 #define pb push_back 3 #define mp make_pair 4 #define esp 1e-14 5 #define lson l, m, rt<<1 6 #define rson m+1, r, rt<<1|1 7 #define sz(x) ((int)((x).size())) 8 #define pf(x) ((x)*(x)) 9 #define pb push_back10 #define in freopen("solve_in.txt", "r", stdin);11 #define bug(x) printf("Line : %u >>>>>>\n", (x));12 #define inf 0x0f0f0f0f13 using namespace std;14 typedef long long LL;15 typedef map<LL, int> MPS;16 typedef pair<LL, LL> PII;17 const int maxn = 20000;18 LL dp[33][maxn];19 int st[10];20 int n, m;21 void pre() {22 st[0] = 1;23 for(int i = 1; i <= 9; i++)24 st[i] = st[i-1]*3;25 }26 int dig[20];27 void getDig(int x) {28 int len = 0;29 memset(dig, 0, sizeof dig);30 while(x) {31 dig[len++] = x%3;32 x /= 3;33 }34 }35 void dfs(int cur, int state, int base, int prestate) {36 if(cur == n) {37 dp[base][state] += dp[base-1][prestate];38 return;39 }40 if(dig[cur] == 0) {41 if(cur+2 < n && dig[cur+1] == 0 && dig[cur+2] == 0) {42 dfs(cur+3, state, base, prestate);43 }44 dfs(cur+1, state+st[cur], base, prestate);45 } else if(dig[cur] == 1) {46 dfs(cur+1, state+2*st[cur], base, prestate);47 } else {48 dfs(cur+1, state, base, prestate);49 }50 }51 int main() {52 // in53 pre();54 while(scanf("%d%d", &n, &m), n || m) {55 if(n*m%3) {56 puts("0");57 continue;58 }59 memset(dp, 0, sizeof dp);60 dp[0][0] = 1;61 for(int i = 1; i <= m; i++) {62 for(int j = 0; j < st[n]; j++) {63 if(dp[i-1][j]) {64 getDig(j);65 dfs(0, 0, i, j);66 }67 }68 }69 printf("%lld\n", dp[m][0]);70 }71 return 0;72 }
另一道类似的题目：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格子，或者不需要覆盖，这样按行进行转移就行了。
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <map> 7 #include <vector> 8 #define pb push_back 9 #define mp make_pair10 #define esp 1e-1411 #define lson l, m, rt<<112 #define rson m+1, r, rt<<1|113 #define sz(x) ((int)((x).size()))14 #define pf(x) ((x)*(x))15 #define pb push_back16 #define in freopen("solve_in.txt", "r", stdin);17 #define bug(x) printf("Line : %u >>>>>>\n", (x));18 #define inf 0x0f0f0f0f19 using namespace std;20 typedef long long LL;21 typedef map<LL, int> MPS;22 typedef pair<LL, LL> PII;23 24 const int M = (int)1e9 + 7;25 const int maxn = 110;26 const int maxm = 1111;27 28 LL dp[maxn][23][maxm];29 int n, m, c, d;30 char maze[maxn][11];31 int dig[11];32 33 void getDig(int x) {34 memset(dig, 0, sizeof dig);35 int len = 0;36 while(x) {37 dig[len++] = x&1;38 x >>= 1;39 }40 }41 bool check(char *s, int x) {42 for(int i = 0; s[i]; i++) {43 if((x&1) && s[i] == ‘0‘) return false;44 x >>= 1;45 }46 return true;47 }48 void dfs(int pre, int num, int st, int cur, int state, int cnt) {49 if(cnt > d) return;50 if(cur == m) {51 dp[pre+1][cnt][state] = (dp[pre+1][cnt][state]+dp[pre][num][st])%M;52 return;53 }54 if(maze[pre+1][cur] == ‘0‘) {55 dfs(pre, num, st, cur+1, state, cnt);56 } else if(dig[cur] == 0) {57 if(cur+1 < m && dig[cur+1] == 0 && maze[pre+1][cur+1] == ‘1‘)58 dfs(pre, num, st, cur+2, state, cnt);59 if(pre+1 < n && maze[pre+2][cur] == ‘1‘)60 dfs(pre, num, st, cur+1, state+(1<<cur), cnt);61 dfs(pre, num, st, cur+1, state, cnt+1);62 } else {63 dfs(pre, num, st, cur+1, state, cnt);64 }65 }66 int main() {67 68 while(scanf("%d%d%d%d", &n, &m, &c, &d) == 4) {69 memset(dp, 0, sizeof dp);70 for(int i = 1; i <= n; i++)71 scanf("%s", maze[i]);72 dp[0][0][0] = 1;73 for(int i = 0; i < n; i++) {74 int j;75 if(i == 0) {76 j = 0;77 getDig(j);78 int x = 0;79 if(dp[i][x][j])80 dfs(i, x, j, 0, 0, x);81 } else {82 for(int j = 0; j < (1<<m); j++) {83 if(check(maze[i], j) == false) continue;84 getDig(j);85 for(int x = 0; x <= d; x++) if(dp[i][x][j])86 dfs(i, x, j, 0, 0, x);87 }88 }89 }90 LL ans = 0;91 for(int i = c; i <= d; i++)92 ans = (ans + dp[n][i][0])%M;93 printf("%lld\n", ans);94 }95 return 0;96 }
ZOJ 2563 Long Dominoes（状压DP）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。