PKU P2411 Mondriaan's Dream

题目描述:

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!

输入格式:

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.

输出格式:

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.

样例输入:

样例输出:

提示:

1<=h,w<=11

时间限制:1000ms
空间限制:256MByte

来源:PKU

这道题本来几个月前就应该做掉的，可是自己那时候太弱了，只有现在重新刷一下了。。。

结果自己写的方法和网上的题解感觉有些不一样，我是用已知的一行去推算下一行的情况；

注意（除第一行）：如果一行中有1，这个1可能代表这两种情况，一种是横着放，一种是上面一排竖下来的（那么上面一排的这个位置肯定是0），所以转移的时候要注意下下；

记住，0永远只代表着从这行竖着向下放的方块！！！（前几个月这个一直没想清楚，还想用三进制的做，真是NAIVE）

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m,f[16][1<<16];
ll maxn;

ll find(ll val)
{
    ll t = 0;
    for(ll i=0;i<m;i++)
    {
        ll ce = 1 << i;
        if(val & ce) t++;
        else
        {
            if(t & 1) return 0;
            t = 0;
        }
    }
    return 1;
}

ll check(ll now , ll down)
{
    ll t = 0;
    for(ll i=0;i<m;i++)
    {
        ll ce = 1 << i;
        if(down & ce)
        {
            if(now & ce)
                t++;
            else
            {
                if(t & 1) return 0;
                t = 0;
            }
        }
        else
        {
            if(!(now & ce)) return 0;
            if(t & 1) return 0;
            t = 0;
        }
    }
    if(t & 1) return 0;
    return 1;
}

int main(){
    while(~scanf("%lld%d",&n,&m))
    {
        if(!n && !m) return 0;
        if(n * m & 1)
        {
            cout<<0<<endl;
            continue;
        }
        memset(f,0,sizeof(f));
        maxn = 1 << m;
        for(ll i=0;i<maxn;i++)
            if(find(i))
                f[1][i] = 1;
        for(ll i=1;i<n;i++)
            for(ll j=0;j<maxn;j++)
            {
                if(f[i][j])
                for(ll k=0;k<maxn;k++)
                {
                    if(check(j , k))
                        f[i + 1][k] += f[i][j];
                }
            }
        printf("%lld
",f[n][maxn-1]);
    }
}

然后这个代码刚好跑过去，吓死我啦。

可是我有想了想，总觉得我这个代码还可以优化。

如果是从这一行推下一行的话，那么第一行为什么还要重新推一次呢？

直接从第〇行开始不就好了吗？？？

还是NAIVE 啊啊啊！

于是我把我的代码删了一部分，修改一点点，真的的就一点点。。。

#include<bits/stdc++.h>
#define ll long long
using namespace std;

ll n,m,f[16][1<<16];
ll maxn;

ll check(ll now , ll down)
{
    ll t = 0;
    for(ll i=0;i<m;i++)
    {
        ll ce = 1 << i;
        if(down & ce)
        {
            if(now & ce)
                t++;
            else
            {
                if(t & 1) return 0;
                t = 0;
            }
        }
        else
        {
            if(!(now & ce)) return 0;
            if(t & 1) return 0;
            t = 0;
        }
    }
    if(t & 1) return 0;
    return 1;
}

int main(){
    while(~scanf("%lld%d",&n,&m))
    {
        if(!n && !m) return 0;
        if(n * m & 1)
        {
            cout<<0<<endl;
            continue;
        }
        memset(f,0,sizeof(f));
        maxn = 1 << m;
        f[0][maxn-1] = 1;
        for(ll i=0;i<n;i++)
            for(ll j=0;j<maxn;j++)
            {
                if(f[i][j])
                for(ll k=0;k<maxn;k++)
                {
                    if(check(j , k))
                        f[i + 1][k] += f[i][j];
                }
            }
        printf("%lld
",f[n][maxn-1]);
    }
}

结果却。。。

还是NAIVE啊！！！