状态压缩类型动态规划-朱全民

状态压缩类型动态规划长沙市雅礼中学朱全民广场铺砖问题•给出一个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的方案数，则•初始值f(1,0)=1•Ans=f[h+1][0]•时间复杂度为O(h*2W)sssifsif的状态能变到其中'),',1(),(基本位操作•若当前状态为s,对s有下列操作：–判断第i位是否为0(S&1i)==0，意思是将1左移i位与s进行与运算后，看结果是否为0.–将第i位置1S|1i，意思是将1左移动i位与s进行或运算.–将第i位置0S&~(1i)，意思是s与第i位为0，其余位为1的数进行与运算。•例如：s=1010101，i=5(S&1i):1010101&0100000=0–S|1i:1010101|0100000=1110101–S&~(1i):1010101&1011111=1010101放置操作•对于每一行有w个位置，所以每一行都有0～2w-1种状态。•对于当前行的状态s，它是由前一行的状态s’转化过来的，显然，对于该行某个位置j：–如果前一行该位置为0,那么该位置可以竖放即0-1–如果前一行连续两个位置为0,那么这两个连续位置可以横放即00-00–如果前一行该位置为1,显然该位置不能再放,于是应该把该位置设置为0，即1-0W=4，h=2的求解过程voiddfs(inti,ints1,ints2,intd){if(s==m)//如第i行已经做完，则累加f[i+1][s2]+=f[i][s1];elseif((jj&(1d))==0)//第d位为0{dfs(i,s1,s2|(1d),d+1);//将第d位变为1，并右移1位//如果第d+1位也为0，则直接搜索d+2位if(s2m-1&&(jj&(1(d+1)))==0)dfs(i,s1,s2,d+2);}elsedfs(i,s1,s2&~(1d),d+1);//将第d位变为0,并右移1位}硬木地板•有一M×N的矩形地板•可以使用的地板砖形状有两种：1)2×1的矩形砖2)2×2中去掉一个1×1的角形砖•你需要计算用这些砖铺满地板共有多少种不同的方案。•必须盖满，地板砖数量足够多，不能存在同时被多个板砖覆盖的部分。•1=M=9,1=N=9分析样例•２×３的地板所有铺法共５种，如下图。•可以看出这题与动归４的“广场铺砖问题”完全类似。只不过这里多了一种砖而已。分析•将矩阵的１行看成一种状态，则某一行矩阵的铺砖情况可以用一个０１串表示：０表示未铺砖，１表示已铺了砖。•该题有两种类型的砖，因此对应６种铺法：•对于上下两行：要能用某种类型的砖铺，必须该砖所覆盖的区域为空。a=a|bin(i)|bin(i+1);b=ba=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)#definebin(i)(1i)/*1左移i位*/#defineemp(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)sssifsif的状态能变到其中'),',1(),(骑士•国际象棋中骑士的移动规则和中国象棋中的马是类似的，它先沿着一个方向移动两格，再沿着与刚才移动方向垂直的方向移动一格。•一个n*n的棋盘需要被摆k个骑士到棋盘上;•那么使所有骑士互不攻击的摆放方式一共有多少种呢？•1≤n≤8样例•如下图，当N=3，K=5时，只有２种方案。分析•类似第１题，我们按行放马，对于上一行的某种状态，看下一行有多少种放法。•因为这里马的个数给定，因此需要增加一维马的个数限制。•由于马的特殊型，马可以控制上下两行，因此每一行的状态是与前两行相关联的，为了计数的方便，采取两行一压的方式，用一个16位整数保存两行的状态。规定高8位保存第一行的状态，低八位保存第二行的状态。•每个格子对应的二进制位如果是1就表示这个格子里放了一个骑士，否则就是没有放。状态冲突处理•定义常量Low=1023，即Low=(000000011111111)2L1=state8L2=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)ssskifsjif的状态能变到其中'),',,1(),,(优化•本题可预先枚举所有的有效状态，即上下两行之间的所有可行状态，放到队列。在动态规划进行决策转移时可直接从队列取出可行状态，这样可以减少很多无效状态的判断。•冲突S(L1,i)&&S(L2,i+2)||S(L1,i+2)&&S(L2,i)总结•以每一行作为1种状态，研究上下两行之间的关系，利用上下两行之间的约束条件进行决策转移。如下图。一般采用一个二进制数表示状态，有时也用三进制或四进制数等。用二进制数表示状态最大的好处就是在决策转移时可以采用位运算，这样能极大提高算法效率。•状态压缩的动态规划实际上也是按常规处理的一种动态规划的做法，只不过由于每一个阶段状态数可能比较多，状态通常采用压缩存储方式，以利于运算和转移。试题的特点一般是数据整体规模较小，或者某一维规模较小。