http://www.cnblogs.com/Lyush/archive/2012/03/23/2413160.html
曾几何时,也写过这一题,那是刚跟着做什么状态压缩dp的时候,1844MS过的,现在终于0MS了.这次的做法有点不一样,首先原来的两个指数级的for循环嵌套,变成一个指数级嵌套一个合法状态的个数,状态的含义也发生了改变,由原来的0,1只表示覆盖,变成了0表示横向覆盖,1表示了纵向覆盖,0和1保留了更多的信息,最后采用了一种退化机制来确保一列中不出现连续的奇数个1,即如果出现了偶数个1的话,那么最后这个1就等价于0,表示下一行下的这一列为0为1均可.那么上一层的合法状态由于发生退化就变成指数级别,但是当前层的合法状态仍然只有少量的一些状态.另一个改动就是不在采用对两个状态的每一个二进制位进行比较,取代的是较快的一次性位运算,这大大缩短了判定两个状态是否合法的时间.
代码如下:
#include <cstdlib> #include <cstring> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; /* 求一个最大11*11的矩形用1*2的瓷砖覆盖的话, 共有多少种覆盖方式,对于任何一个点,都有四种 被覆盖的状态,横着的两种,竖着的两种 动态规划的过程是一层一层进行的因此,我们需要 规定一种状态表示法,使得能够表示四种状态 规定:所有的横着放置的瓷片都由0表示,输出放置 的瓷片都由1来表示,那么就不可能有奇数个连续的 0同时出现的一层,奇数个连续的1出现在一列 我需要计算出每一层所有的可能的放置状态,然后 通过检测相邻两种状态是否以相邻层的关系出现 如果可以,那么就把这种组合情况保留下来,最后 一层就比较特殊,我们在取最后结果的时候,只能够 取最后一层被放置满的哪一种情况 由于行列数较少,使用状态压缩的方式来体现状态 */ int h, w, stu[150], idx; // 11行最多144种状态 long long dp[2][(1<<11)+5]; void dfs(int loc, int statu, int flag) { // flag 用来表示前面有奇数还是偶数个连续的0 if (loc == w) { // 如果前面w(0到w-1列)列都已经填好,并且要求连续偶数个0 if(!flag) { stu[++idx] = statu; } } else { if (flag) { // 如果是奇数个0,则只能够放0 dfs(loc+1, statu, 0); } else { // 否则可放0或者是1 dfs(loc+1, statu, 1); // 放0 dfs(loc+1, statu|(1<<loc), 0); // 放1 } } } void display(int x) { for (int i = w-1; i >= 0; --i) { if (x & 1 << i) printf("1"); else printf("0"); } puts(""); } void match(int r, int pre, int cur) { if ((pre & cur) == pre) { // 凡是要求放置1的位置全部符合要求 dp[r][pre ^ cur] += dp[!r][pre]; } } long long DP() { int lim = 1 << w; memset(dp, 0, sizeof (dp)); for (int i = 0; i <= idx; ++i) { dp[0][stu[i]] = 1; // 那些为1的位,期待一个1来与之匹配,所以不发生退化 } // 初始化第一行的所有状态为1 for (int i = 1; i < h; ++i) { // 从第二层开始计算 // 每一列中,两个0之间不能够有奇数个1,这里采用一个偶数个1退化成0为处理 for (int j = 0; j < lim; ++j) { // 枚举上一层中的所有合法状态(包含退化) for (int k = 0; k <= idx; ++k) { // 放置状态还是不多 if (dp[!(i&1)][j]) { // 如果这个状态在上一行有的话 match(i&1, j, stu[k]); } } dp[!(i&1)][j] = 0; } } return dp[(h-1)&1][0]; } int main() { while (scanf("%d %d", &h, &w), h|w) { if (h & 1 && w & 1) { puts("0"); continue; } if (h < w) h^=w^=h^=w; idx = -1; dfs(0, 0, 0); // 通过输入列为11可知:一层的合法状态其实很少(最多144种) /* for (int i = 0; i <= idx; ++i) { display(stu[i]); }*/ printf("%I64d\n", DP()); } return 0; }