多米诺骨牌解题报告.pdfVIP

多米诺骨牌 [问题描述] 【算法分析】 很容易想到通过状态压缩 每行每列的 情况来动态规划，但这样状 态是 2n+m 的，只能通过部分数据。 这样做为什么会慢呢？有一点是很醒目的，当某一列在之前已经 ，这 时你再添加一个横的，这一列仍然保持 ，二进制状态一点也没变。虽然我也 讲不清为什么这样会慢，但是直觉……所以想通过计算补集，即有多少种方案列 不连通。这里是可以用容斥原理做的，用 S 表示至少有 i 列不 的方案，那么 i i m-1 我们要计算的就是 S -S +S ……+(-1) S +……+(-1) S 。那么怎么求有 S 呢? 0 1 2 i m-1 i 下面以 S 为例，其它情况类推。 2 对于至少要两列不连通的情况，我们枚举这两列，将矩形分成 A 、A 、A 1 2 3 这三个区域。现在我们要计算有多少种方案满足每一行都 。对于某一行只要 这三个中任意一个那一行是 的即可，所以这三个矩形我们要 考虑。用 F[i]表示从第 1 行到第 i 行都 的方案数。我们先计算第一行到第 i 行随意摆放 骨牌的方案数，然后减去某一行不连通的方案数。我们枚举第一个不连通的行j ， 那么需要减去的方案数为 F[j]乘以 j+1 行到 i 行随意摆放骨牌的方案数，所以 。其中 Sum[A,i,j]表示子矩形A 的第 i 行到第j 行的孙子矩形里算意摆放骨牌的方案数， F[0]=-1。 接下来我们只要预处理Sum数组就能在2m ×nm 的时间复杂度内解决此问 题。由于我们要计算所有子矩形中随意摆放骨牌的方案数，所以还是会超时。但 事实上当我们确定左边界、有边界、上边界后，所有矩形的 Sum 值可以在一次 2 m 状态压缩动态规划中一起计算。至此此题已经解决，时间复杂度O(nm ×nm2 )。 【总结】 这是一道很难的统计题，很难跳出状态压缩的定式从容斥的角度来统计，并 且那个在计算行 方案数时的递推也相当巧妙。 【程序】 program ex1; const p type tk=array[0..20,0..20] of longint; var map,mmap:tk; f:array[0..20,0..20,0..1 shl 15] of longint; sum:array[0..20,0..20,0..20,0..20] of longint; s,e:array[0..20] of longint; tot,x1,y1,x2,y2,i,j,k,l,m,n,xys,lhh:longint; ch:char; procedure calc(var a:tk;n,m:longint); //状态压缩计算矩形 a 中随便摆放骨牌的方案数 var ii,jj,kk,ll,mm,nn:longint; begin for ii:=0 to n+1 do for jj:=0 to m do