[HIHO] 1048 铺地板

历经千辛万苦，小Hi和小Ho终于到达了举办美食节的城市！虽然人山人海，但小Hi和小Ho仍然抑制不住兴奋之情，他们放下行李便投入到了美食节的活动当中。美食节的各个摊位上各自有着非常多的有意思的小游戏，其中一个便是这样子的：

小Hi和小Ho领到了一个大小为N*M的长方形盘子，他们可以用这个盒子来装一些大小为2*1的蛋糕。但是根据要求，他们一定要将这个盘子装的满满的，一点缝隙也不能留下来，才能够将这些蛋糕带走。

这么简单的问题自然难不倒小Hi和小Ho，于是他们很快的就拿着蛋糕离开了~

但小Ho却不只满足于此，于是他提出了一个问题——他们有多少种方案来装满这个N*M的盘子呢？

值得注意的是，这个长方形盘子的上下左右是有区别的，如在N=4, M=3的时候，下面的两种方案被视为不同的两种方案哦！



提示：我们来玩拼图吧！不过不同的枚举方式会导致不同的结果哦！

输入

每个测试点（输入文件）有且仅有一组测试数据。

每组测试数据的第一行为两个正整数N、M，表示小Hi和小Ho拿到的盘子的大小。

对于100%的数据，满足2<=N<=1000, 3<=m<=5。<>

输出

考虑到总的方案数可能非常大，只需要输出方案数除以1000000007的余数。

样例输入

2 4

样例输出

5

状压DP，令1为竖着放的头，其余为0。

预处理每行连续0的个数的奇偶性

条件

1.连续0个数为偶数

2.两行1不能重合（&结果为0）

三重循环转移，最后一行一定不能再开始放竖着的方块了，所以0状态就是答案。

//Stay foolish,stay hungry,stay young,stay simple

#include<iostream>

using namespace std;

const int MAXN=20000;

bool ok[MAXN];

int n,m;

int f[1005][128];

int main(){

    cin>>n>>m;

    for(int i=0;i<(1<<m);i++){

        bool flag=0;

        bool ans=0,cnt=0;

        for(int k=0;k<m;k++){

            if((i>>k)&1){

                ans|=cnt;

                cnt=0;

            }else cnt^=1;

        }

        ans|=cnt;

        ok[i]=!ans;

    }

    f[0][0]=1;

    for(int i=1;i<=n;i++){

        for(int j=0;j<(1<<m);j++){

            for(int k=0;k<(1<<m);k++){

                if(!ok[j|k]) continue;

                if((j&k)) continue;

                f[i][j]+=f[i-1][k];

                f[i][j]%=1000000007;

            }

        }

    }

    cout<<f[n][0]%1000000007<<endl;

    return 0;

}

巴特西

[HIHO] 1048 铺地板

最新文章

热门文章