【POJ2411】Mondriaan's Dream

题意:

给出n*m的方阵,求用1*2的小矩形铺满有几种情况。

题解:

这题可以用状压dp来解决,但现在我用的是轮廓线dp(状压dp的一种,但在这题中比状压dp更优)。

我们可以从左到右、从上到下把方阵分成n*m个阶段。由于小矩形是1 * 2的, 所以对于每个阶段的决策有影响的只有当前这一行和上一行的一些部分。而上面“#”的部分是已经确定的,对当前点没有影响

如:1 2 3 4 5

1      # # # # #

2      # # 1 1 1

3      0 0 ?

·······

把对于决策有影响的阶段称为轮廓线(如上图的11100)

于是,可以用2^(m -1)来枚举轮廓线的状态。(m < n)

1表示被覆盖,0表示没被覆盖。

设(i, j)为当前阶段,k为当前轮廓线的状态

则可以得到转移方程:
不放: 下一个状态 now =  (k << 1) & ( (1 << m)  -  1)
dp[cur][now] += dp[cur ^ 1][k];

条件k&(1 << (m - 1))[即 [i-1][j]一定要被覆盖]
向上放: 下一个状态 now = ( (k << 1) | 1) & ( (1 << m)  - 1)
dp[cur][now] += dp[cur ^ 1][k];

条件!(k&(1 << (m - 1)))[即 [i-1][j]一定没被覆盖]
向左放: 下一个状态 now = ((k << 1)|3)&((1 << m) - 1)
dp[cur][now] += dp[cur ^ 1][k];

条件k&(1 << (m - 1)) && !(k&1)[即 [i-1][j]一定要被覆盖,[i][j-1]一定不能被覆盖]

时间复杂度O(n*m*2^m),由于一个点的状态只由它前一个点的状态转移来,可以开滚动数组来存储答案,最后答案dp[cur][2^m-1]

代码如下:

继续阅读【POJ2411】Mondriaan's Dream