首页 > 代码库 > POJ2411 Mondriaan's Dream

POJ2411 Mondriaan's Dream

2024-08-13 13:31:02   225人阅读

Description

Squares and rectangles fascinated the famous Dutch painter Piet Mondriaan. One night, after producing the drawings in his ‘toilet series‘ (where he had to use his toilet paper to draw on, for all of his paper was filled with squares and rectangles), he dreamt of filling a large rectangle with small rectangles of width 2 and height 1 in varying ways.
技术分享

Expert as he was in this material, he saw at a glance that he‘ll need a computer to calculate the number of ways to fill the large rectangle whose dimensions were integer values, as well. Help him, so that his dream won‘t turn into a nightmare!

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

技术分享For each test case, output the number of different ways the given rectangle can be filled with small rectangles of size 2 times 1. Assume the given large rectangle is oriented, i.e. count symmetrical tilings multiple times.

Sample Input

1 21 31 42 22 32 42 114 110 0

Sample Output

10123514451205

Source

Ulm Local 2000
 
 
 
正解：轮廓线动态规划
解题报告：
　　轮廓线动态规划第一题，我觉得有必要好好总结一下。
　　白书上的第六章第一题，尽管没有图的说明的情况下很难说清楚，但是我还是试图讲清楚。
　　状态可以用二进制维护，首先我们对于每一个格子都可以表示是否被覆盖。而且不难想到，对于n×m的棋盘，只有上方和左方的共m个格子会产生影响，以前的必须已经被覆盖。
　　所以我们考虑根据前m个格子的状态对现在进行决策，对于每个格子，显然可以不放（等于是等着右边的或者下面的来覆盖它），那么必须要满足的条件就是上方已经被覆盖，否则不合法；可以往左放，那么左边必须未被覆盖，且上方已经被覆盖；往上放，则只需上方未被覆盖即可。
　　因为设计二进制表示状态，所以用位运算会很方便。
　　另外，转移的话其实最优的不是枚举所有状态，而是类似于BFS的广搜转移，不再赘述。
 
 1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector>10 #include <queue>11 #include <map>12 #include <set>13 using namespace std;14 typedef long long LL;15 const int MAXN = 11;16 const int MAXS = (1<<11);17 int n,m;18 LL f[2][MAXS];19 20 inline void solve(){21     memset(f,0,sizeof(f));22     int end=(1<<m)-1; int tag=1;23     f[1][end]=1;//注意初值的设定！！！24     for(int i=0;i<n;i++)25     for(int j=0;j<m;j++){26         tag^=1; memset(f[tag],0,sizeof(f[tag]));27         for(int k=0;k<=end;k++) {28         if((k<<1)&(1<<m)) f[tag][(k<<1)^(1<<m)]+=f[tag^1][k];//这一个格子不放29         if(i && ( !((k<<1)&(1<<m)) )) f[tag][(k<<1)^1]+=f[tag^1][k];//往上放30         if(j && (!(k&1)) && ((k<<1)&(1<<m))) f[tag][(k<<1)^3^(1<<m)]+=f[tag^1][k];//往左放31         }32     }33     printf("%lld\n",f[tag][end]);34 }35 36 inline void work(){37     while(1) {38     scanf("%d%d",&n,&m); if(n==0 && m==0) break;39     if((n*m)%2==1) { printf("0\n"); continue; }40     if(n<m) swap(n,m); 41     solve();42     }43 }44 45 int main()46 {47   work();48   return 0;49 }

 

POJ2411 Mondriaan's Dream


联系
我们