POJ 2411 Mondriaan's Dream (状压dp)

POJ 2411 Mondriaan's Dream (状压dp)

Description

Input

The input contains several test cases. Each test case is made up of two integer numbers: the height h and the width w of the large rectangle. Input is terminated by h=w=0. Otherwise, 1<=h,w<=11.

Output

Sample Input

1 21 31 42 22 32 42 114 110 0

Sample Output

10123514451205

题意

给出一个 ​​n*m​​​ 的方格，问用 ​​1*2​​ 的小方格来填充总共有多少种方法。

思路

我们定义 ​​dp[i][j]​​​ 代表第 ​​i-1​​​ 行已经放满，第 ​​i​​​ 行状态为 ​​j​​ 时候的方案数。

其中每一行的状态我们可以用一个二进制来表示， ​​0​​​ 代表未填充， ​​1​​ 代表已填充。

因为方块有两种摆放形式：竖放、横放

所以当第 ​​i​​​ 行第 ​​j​​​ 列竖放一个方块时，第 ​​i-1​​​ 行第 ​​j​​​ 列需要留空；而当第 ​​i​​​ 行第 ​​j​​​ 列与第 ​​j+1​​​ 列横放一个方块时，第 ​​i-1​​​ 行第 ​​j​​​ 列与第 ​​j+1​​​ 列则需已填充，因为我们定义的 ​​dp​​​ 需要把第 ​​i-1​​ 行全部放满。

状态转移方程： dp[i][s]=sum(dp[i−1][si]) 其中状态 ​​s​​​ 与状态 ​​si​​​ 必须兼容，也就是状态 ​​s​​​ 中竖放的块能够填满状态 ​​si​​ 中的空。

这里有一个优化，也就是当 n∗m

AC 代码

#include#include#include#includeusing namespace std;#define MAX ((1<<11)+10)typedef __int64 LL;int n,m;LL dp[15][MAX];LL ans[15][15];bool jud(int x) // 判断 x 二进制中是否存在独立的1{ bool is1=false; for(int i=0; i>n>>m&&(n||m)) { if(ans[n][m]) //如果之前计算过，则直接给出结果 { printf("%I64d\n",ans[n][m]); continue; } if(n&1&&m&1) // 如果两边长都为奇数，则其面积也是奇数，无法放置 { printf("0\n"); continue; } solve(); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。