找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1662|回复: 1
收起左侧

[资源分享] 39 Cover The Magic Board

[复制链接]

62

主题

1

精华

202

积分

高级会员

Rank: 3Rank: 3

积分
202
发表于 6-10-2015 03:24 AM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 qb2008 于 6-10-2015 03:25 AM 编辑

这道可以算动态规划题。开始是用简单的动态规划,枚举一行中各列的状态,然后从前一行推到后一行,一直推到第n行。算法时间复杂度是
O(n*3^m)。超时了,用java写估计上10^9就危险了,c++或许会好一点。不过测试中竟然有个大坑,n的取值范围在题目中明明说的是<10^6,
结果测试中蹦出个10^9,看了测试结果才发现所有线性时间复杂度及以上的都不行。于是只能想log(n)的解法。
因为题中每行情况都是一样的,可以随便拼,那最简单的想法就是不要一行一行地拼,而是好多行在一起一块一块地拼。然后我发现问题的难点
出现在如何处理拼接行上。假设一块是i行到j行,另一块是j行到k行,理论上是可以枚举一下第j行的可能分法,然后把一部分分给上一块,另一部分
分给下一块。但这样是有重复的。分法不一样不代表最终的覆盖方法就不一样。所以实际上我们要枚举的是第j行和第j+1行所有可能的覆盖方法。
我发现题中其实给了便利,默认方法是1*1地覆盖,这种方法我们不用考虑,只要把2*2的覆盖方法枚举一遍就行了。
在两行中枚举所有2*2的覆盖方法,假设有typeNum种,我发现每种对应一个覆盖前上一行状态aboveState, 一个覆盖下一行状态belowState。如果上
一行不是处于aboveState中的一个,它肯定要通过加些1*1变成一种aboveState,下一行亦然。这样解法就清晰多了。我把多行组成一块,有一个最高
行的列状态,有一个最低行的列状态,最高行列状态肯定是belowState中的一个(其它最高行列状态可以通过粘1*1转化成belowState),最低行列
状态肯定是aboveState中的一个(其它最低行列状态可以通过粘1*1转化成aboveState)。在把两块合并到一起时使用同一个2*2覆盖方法对应的aboveState和belowState,这样就可以保证块合并时不重复了。
然后问题就简单了,用2分法可以在O(logn)时间内把1行,2行,4行一直到n行的覆盖方法算出来。typeNum不会超过2^m, 块合并时最多2^(3*m),
所以时间复杂度可看为O(logn*2^(3*m))。还是感觉这解法我都有些难以理解,有简单的方法欢迎指教。
代码如下,上面是超时的动态规划,后面是通过的二分:
  1. public class CoverTheMagicBoard {
  2.   final long MOD = 10000007;
  3.   public int coverBoard0(int N, int M) {
  4.     if (M == 0) {
  5.       return 0;
  6.     }

  7.     int maxState = (1 << M) - 1;
  8.     // dp【i】[j] means the number of ways to achieve state j in row i.
  9.     // state j, for each bit k, if (j & (1 << k)), column k is covered, otherwith column k is not covered.
  10.     int[][] dp = new int[N][maxState + 1];
  11.     for (int i = 0; i <= maxState; ++i) {
  12.       dp[0]【i】 = 1;
  13.     }
  14.     for (int i = 1; i < N; ++i) {
  15.       permuteState(dp, i, 0, 0, 0, M);
  16.     }
  17.     return dp[N - 1][maxState];
  18.   }

  19.   void permuteState(int[][] dp, int curRow, int curCol, int targetState, int prevState, int M) {
  20.     if (curCol == M) {
  21.       dp[curRow][targetState] = (int)((dp[curRow][targetState] + dp[curRow - 1][prevState]) % MOD);
  22.       return;
  23.     }
  24.     // Don't cover (curRow, curCol).
  25.     permuteState(dp, curRow, curCol + 1, targetState, prevState | (1 << curCol), M);
  26.     // Cover (curRow, curCol) with 1 * 1.
  27.     permuteState(dp, curRow, curCol + 1, targetState | (1 << curCol), prevState | (1 << curCol), M);
  28.     // Cover (curRow, curCol) with 2 * 2.
  29.     if (curCol < M - 1) {
  30.       permuteState(dp, curRow, curCol + 2, targetState | (3 << curCol), prevState, M);
  31.     }
  32.   }

  33.   public int coverBoard(int N, int M) {
  34.     if (M == 0) {
  35.       return 0;
  36.     }

  37.     int maxState = (1 << M) - 1;
  38.     long[][] nearDown = new long[maxState + 1][maxState + 1];
  39.     for (int i = 0; i <= maxState; ++i) {
  40.       for (int j = 0; j <= maxState; ++j) {
  41.         long[] count = new long[M + 1];
  42.         count[0] = 1;
  43.         int pa = 1;
  44.         int pb = 0;
  45.         for (int k = 1; k <= M; ++k) {
  46.           int a = (i >> (k - 1)) & 1;
  47.           int b = (j >> (k - 1)) & 1;
  48.           if (a == 0) {
  49.             if (b == 0) {
  50.               count[k] = (count[k] + count[k - 1]) % MOD;
  51.             } else if (b == 1) {
  52.               count[k] = (count[k] + count[k - 1]) % MOD;
  53.               if (pa == 0 && pb == 1) {
  54.                 count[k] = (count[k] + count[k - 2]) % MOD;
  55.               }
  56.             }
  57.           } else if (a == 1) {
  58.             count[k] = (count[k] + count[k - 1]) % MOD;
  59.           }
  60.           pa = a;
  61.           pb = b;
  62.         }
  63.         nearDown【i】[j] = count[M];
  64.       }
  65.     }

  66.     ArrayList<int[]> interact = new ArrayList<int[]>();
  67.     permuteInteract(0, 0, 0, M, interact);

  68.     int interactNum = interact.size();
  69.     long[][][] dp = new long[32][interactNum][interactNum];

  70.     for (int i = 0; i < interactNum; ++i) {
  71.       for (int j = 0; j < interactNum; ++j) {
  72.         // From below i to above j.
  73.         int belowState = interact.get(i)[1];
  74.         int aboveState = interact.get(j)[0];
  75.         dp[1]【i】[j] = nearDown[belowState][aboveState];
  76.       }
  77.     }
  78.     for (int p = 2; p <= 31; ++p) {
  79.       for (int i = 0; i < interactNum; ++i) {
  80.         for (int j = 0; j < interactNum; ++j) {
  81.           for (int k = 0; k < interactNum; ++k) {
  82.             // From below i to above j, go through above k and below k.
  83.             dp[p]【i】[j] = (dp[p]【i】[j] + dp[p-1]【i】[k] * dp[p-1][k][j]) % MOD;
  84.           }
  85.         }
  86.       }
  87.     }
  88.     long[] cur = new long[interactNum];
  89.     for (int i = 0; i < interactNum; ++i) {
  90.       int aboveState = interact.get(i)[0];
  91.       cur【i】 = nearDown[maxState][aboveState];
  92.     }
  93.     int last = N - 1;
  94.     for (int p = 1; (1L << p) <= last; ++p) {
  95.       if ((last & (1 << p)) == 0) {
  96.         continue;
  97.       }
  98.       long[] next = new long[interactNum];
  99.       for (int i = 0; i < interactNum; ++i) {
  100.         for (int j = 0; j < interactNum; ++j) {
  101.           // cur【i】(above i) -> below i -> above j.
  102.           next[j] = (next[j] + cur【i】 * dp[p]【i】[j]) % MOD;
  103.         }
  104.       }
  105.       cur = next;
  106.     }
  107.     long result = 0;
  108.     if ((last & 1) == 0) {
  109.       for (int i = 0; i < interactNum; ++i) {
  110.         if (interact.get(i)[0] == maxState) {
  111.           result = cur【i】;
  112.         }
  113.       }
  114.     } else {
  115.       for (int i = 0; i < interactNum; ++i) {
  116.         result = (result + cur【i】) % MOD;
  117.       }
  118.     }
  119.     return (int)result;
  120.   }

  121.   void permuteInteract(int pos, int aboveState, int belowState, int M, ArrayList<int[]> interact) {
  122.     if (pos == M) {
  123.       interact.add(new int[]{aboveState, belowState});
  124.       return;
  125.     }
  126.     // don't use 2 * 2 between above and below.
  127.     permuteInteract(pos + 1, aboveState | (1 << pos), belowState, M, interact);
  128.     // use 2 * 2 between above and below.
  129.     if (pos < M - 1) {
  130.       permuteInteract(pos + 2, aboveState, belowState | (3 << pos), M, interact);
  131.     }
  132.   }
  133. }
复制代码



781

主题

575

精华

5670

积分

顶级版主

Rank: 9Rank: 9Rank: 9

积分
5670

活跃会员热心会员优秀版主

发表于 6-10-2015 01:25 PM | 显示全部楼层
感谢您的分享~~~祝您面试工作学习顺利~~~精华贴~~~
我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表