ZOJ 2563 Long Dominoes（状压DP）

给定一个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 ;

 }

巴特西

ZOJ 2563 Long Dominoes（状压DP）

最新文章

热门文章