远航休息栈
首页 > 题解 > poj 2411 Mondriaan’s Dream

poj 2411 Mondriaan’s Dream

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.

images
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.

images

Sample Input

1 2
1 3
1 4
2 2
2 3
2 4
2 11
4 11
0 0

Sample Output

1
0
1
2
3
5
144
51205

题意

用12和21的小块覆盖矩阵。。。

题解

1， 因为小的矩形为12或21，那么由这两种构成的大矩形的面积必然为偶数，所以我们可以知道若是n*m为奇数，那么答案必然为0.

2， 那么我们如今来解析小矩形的摆放景象： ①横着放   ②和上方一行一路竖着放  ③和下面一路竖着放。

a：

1   1   来默示横放了一个矩形；
b：

0

1　　   来默示和上方一行一路竖着放了一个矩形；

c：

1

0　　   默示和下面一行一路放了一个矩形；

总结 ：至于为什么这么放呢，因为如许 才干够区分出怎么放的,你可以动手画画，在所有画出来的图中，只有以上三种矩形的摆放形式！

3， 那么按照矩形的摆放的形式，我们知道当前行只会受到上方一行的影响。那么我们用dp[i][j]默示前i-1行已经摆放好的景象下第i行的状况为j时的摆放数，那么我们知道dp[i][j] += dp[i-1][k] （k是i-1所有满足的状况）。如今我们就是去解析每一行的状况了，我们利用二进制的思惟，因为有m 列，那么每一行的最多的状况数为（1<<m）-1个，所以我们就可以经由过程列举去求出每一行的满足的前提，最后的答案就是dp[n-1][（1<<m）-1]（n是从0开始的）.

4， 如今推敲第i行j列这个dp[i][j]式子:（有点类似枚举的意思）

① 若是是横放矩形，那么就是这一行和上方一行的i和j都是1  ；（可能你会有疑问，为啥不可能是竖着摆放，那就再好好想想那三种摆放形式，当前状况已是横放，所以那两种竖放的小矩形形式不可能再出现了，仔细详细）

② 若是是竖放有两种景象：若是是和上一行竖放那么这一行的j列为1，上一行的j列为0 ； 若是是和下一行竖放的，那么就是这一行的j列为0，下一行必然为要为1才能满足要求；

5， 初始化第一行，这特殊的一行，因为第一行是没有前面一行的。所以必须先预处理出第一行满足的所有的状况，然后列举 1 ~ n-1 行。

6， 这里求出每一行的满足的状况时有两种思路：①是经由过程dfs的思路，直接搜出所有的可能满足的状况  ②直接暴力列举1-（1<<m）-1所有的状况。

#include <cstdio>
#include <cstring>
using namespace std;
int n,m;
long long dp[110][1<<12];
void init(int now,int sat)
{
    if (now==m)
    {
        dp[0][sat]=1;
        return;
    }
    if (now+1<=m)
        init(now+1,sat<<1);
    if (now+2<=m)
        init(now+2,sat<<2|3);
}
void dfs(int now,int cur,int pre,int pos)
{
    if (pos==m)
    {
        dp[now][cur]+=dp[now-1][pre];
        return;
    }
    if (pos+1<=m)
    {
        dfs(now,cur<<1,pre<<1|1,pos+1);
        dfs(now,cur<<1|1,pre<<1,pos+1);
    }
    if (pos+2<=m)
        dfs(now,cur<<2|3,pre<<2|3,pos+2);
}
main()
{
    while(1)
    {
        scanf("%d%d",&n,&m);
        if (m==0&&n==0)
            return 0;
        if (n*m&1)
        {
            printf("0n");
            continue;
        }
        memset(dp,0,sizeof dp);
        init(0,0);
        for (int i=1;i<n;i++)
            dfs(i,0,0,0);
        printf("%I64dn",dp[n-1][(1<<m)-1]);
    }
}

第二种写法

来自discuss

#include <iostream>
using namespace std;
long long f[11][1<<11];
int n,m;
int main()
{
 f[1][1] =0;
 f[1][2] =1;
 f[1][3] =0;
 f[1][4] =1;
 f[1][5] =0;
 f[1][6] =1;
 f[1][7] =0;
 f[1][8] =1;
 f[1][9] =0;
 f[1][10] =1;
 f[1][11] =0;
 f[2][1] =1;
 f[2][2] =2;
 f[2][3] =3;
 f[2][4] =5;
 f[2][5] =8;
 f[2][6] =13;
 f[2][7] =21;
 f[2][8] =34;
 f[2][9] =55;
 f[2][10] =89;
 f[2][11] =144;
 f[3][1] =0;
 f[3][2] =3;
 f[3][3] =0;
 f[3][4] =11;
 f[3][5] =0;
 f[3][6] =41;
 f[3][7] =0;
 f[3][8] =153;
 f[3][9] =0;
 f[3][10] =571;
 f[3][11] =0;
 f[4][1] =1;
 f[4][2] =5;
 f[4][3] =11;
 f[4][4] =36;
 f[4][5] =95;
 f[4][6] =281;
 f[4][7] =781;
 f[4][8] =2245;
 f[4][9] =6336;
 f[4][10] =18061;
 f[4][11] =51205;
 f[5][1] =0;
 f[5][2] =8;
 f[5][3] =0;
 f[5][4] =95;
 f[5][5] =0;
 f[5][6] =1183;
 f[5][7] =0;
 f[5][8] =14824;
 f[5][9] =0;
 f[5][10] =185921;
 f[5][11] =0;
 f[6][1] =1;
 f[6][2] =13;
 f[6][3] =41;
 f[6][4] =281;
 f[6][5] =1183;
 f[6][6] =6728;
 f[6][7] =31529;
 f[6][8] =167089;
 f[6][9] =817991;
 f[6][10] =4213133;
 f[6][11] =21001799;
 f[7][1] =0;
 f[7][2] =21;
 f[7][3] =0;
 f[7][4] =781;
 f[7][5] =0;
 f[7][6] =31529;
 f[7][7] =0;
 f[7][8] =1292697;
 f[7][9] =0;
 f[7][10] =53175517;
 f[7][11] =0;
 f[8][1] =1;
 f[8][2] =34;
 f[8][3] =153;
 f[8][4] =2245;
 f[8][5] =14824;
 f[8][6] =167089;
 f[8][7] =1292697;
 f[8][8] =12988816;
 f[8][9] =108435745;
 f[8][10] =1031151241;
 f[8][11] =8940739824;
 f[9][1] =0;
 f[9][2] =55;
 f[9][3] =0;
 f[9][4] =6336;
 f[9][5] =0;
 f[9][6] =817991;
 f[9][7] =0;
 f[9][8] =108435745;
 f[9][9] =0;
 f[9][10] =14479521761;
 f[9][11] =0;
 f[10][1] =1;
 f[10][2] =89;
 f[10][3] =571;
 f[10][4] =18061;
 f[10][5] =185921;
 f[10][6] =4213133;
 f[10][7] =53175517;
 f[10][8] =1031151241;
 f[10][9] =14479521761;
 f[10][10] =258584046368;
 f[10][11] =3852472573499;
 f[11][1] =0;
 f[11][2] =144;
 f[11][3] =0;
 f[11][4] =51205;
 f[11][5] =0;
 f[11][6] =21001799;
 f[11][7] =0;
 f[11][8] =8940739824;
 f[11][9] =0;
 f[11][10] =3852472573499;
 f[11][11] =0;
while (scanf("%d%d", &n, &m), (n | m) >0)
 printf("%lldn", f[n][m]);
return0;
}

images