5状态压缩类型动态规划

null状态压缩类型 动态 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 状态压缩类型 动态规划 长沙市雅礼中学 朱全民广场铺砖问题广场铺砖问题给出一个W行H列的广场 用1*2小砖铺盖，小砖之间互相不能重叠 问有多少种不同的铺法？ 1<=W，H<=11分析分析该题给出的广场的面积很小，给出了一种1*2的砖，问用砖去铺广场有多少种铺法？ 因为w,h<=11,很容易想到采用搜索的方法，可以采用深搜或宽搜均可。 尽管w,h<=11，不很大，但是用1*2的砖铺，深度最大可达到11，这样，如果采用深搜，对于每一层都需要回溯，时间复杂度也很高。 如果采用宽搜，每一个点都有2种铺法，因此可以扩展出2个结点，要求所有的解，必须扩展全部树结构，如果11层结点，是个完全二叉树，结点数量可达211*11 =2121 ，无论空间和时间都难以承受。 因此我们需要采用其他方法。进一步分析进一步分析性质1：如果w和h都是奇数，则无解，否则有解。 证明：w,h都是奇数，则w*h也是奇数，由于1×2的砖有2块，因此无论铺多少块都是偶数，因此不能覆盖所有的地板。如果地板的面积S是偶数，肯定能被2整除，因此可以用S/2块砖铺满整个地板。 性质2：对于每铺一次地板，只会影响所铺的上下两行。 证明：因为是1×2的砖铺，性质显然。 性质3：如果按行铺地板，每一行的铺法都类似。 证明：显然！ 一个示例一个示例一个6×9的面积铺法如下图: 可以看出，在按行铺的过程中，某些砖会分成两半，如图2，但最多也是向下突出一格，在图3中，我们将图2的空隙填满，则又转移到了下一种状态。状态的表示状态的表示如果我们把行进行动态规划，则第i行的各种情况即表示第i个阶段的的各种状态。 若某格被铺了砖，则用1表示，没有铺砖，则用0表示，那么行的状态就是一个w个格子的0,1串，即w位的二进制数。如下图状态为：100100 下面就是由某个二进制数能转化到另一个二进制数的问题了。如下图,状态由100100  111100 和110100 ：动态规划动态规划显然，对于每一行,宽度为w,每格可放0和1，因此有2w 种状态，如下图： 设f(i,s)表示铺到第i行，状态为s的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 数，则 初始值f(1,0)=1 Ans=f[h+1][0] 时间复杂度为O(h*2W) 基本位操作基本位操作若当前状态为s,对s 有下列操作： 判断第i位是否为0  (S & 1 << i) == 0，意思是将1左移i位与s进行与运算后，看结果是否为0. 将第i位置1  S | 1 << i，意思是将1左移动i位与s进行或运算. 将第i位置0  S & ~(1 << i)，意思是s与第i位为0，其余位为1的数进行与运算。 例如：s=1010101，i=5 (S & 1 << i): 1010101 & 0100000 = 0 S | 1 << i: 1010101 | 0100000 = 1110101 S & ~(1 << i): 1010101 & 1011111 = 1010101 放置操作放置操作对于每一行有w个位置，所以每一行都有0～2w-1种状态。 对于当前行的状态s，它是由前一行的状态s’转化过来的，显然，对于该行某个位置j： 如果前一行该位置为0,那么该位置可以竖放 即 0-> 1 如果前一行连续两个位置为0,那么这两个连续位置可以横放 即00-> 00 如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0 ，即1-> 0 nullW=4，h=2的求解过程nullvoid dfs(int i, int s1, int s2, int d) { if (s == m) //如第i行已经做完，则累加 f[i + 1][s2] += f[i][s1]; else if ((jj & (1 << d)) == 0) //第d位为0 { dfs(i,s1, s2| (1 << d), d + 1); //将第d位变为1，并右移1位 //如果第d+1位也为0，则直接搜索d+2位 if (s2 < m - 1 && (jj & (1 << (d + 1))) == 0) dfs(i,s1, s2, d + 2); } else dfs(i, s1,s2 & ~(1 << d), d + 1); //将第d位变为0,并右移1位 }硬木地板硬木地板 有一M×N 的矩形地板 可以使用的地板砖形状有两种： 1) 2×1的矩形砖 2) 2×2中去掉一个1×1的角形砖 你需要计算用这些砖铺满地板共有多少种不同的方案。 必须盖满，地板砖数量足够多，不能存在同时被多个板砖覆盖的部分。 1<=M<=9, 1<=N<=9分析样例分析样例２×３的地板所有铺法共５种，如下图。 可以看出这题与动归４的“广场铺砖问题”完全类似。只不过这里多了一种砖而已。 分析分析将矩阵的１行看成一种状态，则某一行矩阵的铺砖情况可以用一个０１串表示：０表示未铺砖，１表示已铺了砖。 该题有两种类型的砖，因此对应６种铺法： 对于上下两行：要能用某种类型的砖铺，必须该砖所覆盖的区域为空。 null a= a | bin(i) | bin(i + 1); b=b a =a | bin(i) | bin(i + 1); b= b | bin(i) a =a | bin(i) | bin(i + 1); b= b | bin(i+1) a= a | bin(i) ; b= b | bin(i) a= a | bin(i) ;b= b | bin(i) | bin(i - 1) a= a | bin(i) ; b= b | bin(i) | bin(i + 1) #define bin(i) (1 << i) /*1左移i位*/ #define emp(a,i) (!(a & bin(i))) /*判断a的i位是否位0*/动态规划动态规划设f(i,s)表示第i行的状态为s时可达的方案数，则： 初始值f(1,0)=1 Ans=f[h+1][0] 时间复杂度为O(h*2W) 骑士骑士国际象棋中骑士的移动规则和中国象棋中的马是类似的，它先沿着一个方向移动两格，再沿着与刚才移动方向垂直的方向移动一格。 一个n*n的棋盘需要被摆k个骑士到棋盘上; 那么使所有骑士互不攻击的摆放方式一共有多少种呢？ 1≤n≤8样例样例如下图，当N=3，K=5时，只有２种方案。分析分析类似第１题，我们按行放马，对于上一行的某种状态，看下一行有多少种放法。 因为这里马的个数给定，因此需要增加一维马的个数限制。 由于马的特殊型，马可以控制上下两行，因此每一行的状态是与前两行相关联的，为了计数的方便，采取两行一压的方式，用一个16位整数保存两行的状态。规定高8位保存第一行的状态，低八位保存第二行的状态。 每个格子对应的二进制位如果是1就表示这个格子里放了一个骑士，否则就是没有放。状态冲突处理状态冲突处理定义常量Low=1023，即Low=(000000011111111)2 L1 = state << 8 L2 = state & Low 则这两句就将第一行的状态存入了L1，第二行的状态存入了L2。 下列产生冲突： S(L1,i) & S’(L1,i+1) S(L1,i) & S’(L2,i+2) S(L2,i) & S’(L2,i+1) 动态规划动态规划设f(i,j,s)表示前2i行放了j个马的最多方案数，则： 设sum1(s)表示状态s中１的个数，上式需满足j=k+sum1(s) && s’与s不冲突. Answer=∑f[n/2][j][s]。 时间复杂度O(n*k*22N) 优化优化本题可预先枚举所有的有效状态，即上下两行之间的所有可行状态，放到队列。在动态规划进行决策转移时可直接从队列取出可行状态，这样可以减少很多无效状态的判断。 冲突 S(L1,i) && S(L2,i+2) || S(L1,i+2) && S(L2,i) 　　总结总结以每一行作为1种状态，研究上下两行之间的关系，利用上下两行之间的约束条件进行决策转移。如下图。一般采用一个二进制数表示状态，有时也用三进制或四进制数等。用二进制数表示状态最大的好处就是在决策转移时可以采用位运算，这样能极大提高算法效率。 状态压缩的动态规划实际上也是按常规处理的一种动态规划的做法，只不过由于每一个阶段状态数可能比较多，状态通常采用压缩存储方式，以利于运算和转移。试题的特点一般是数据整体规模较小，或者某一维规模较小。