Mondriaan's Dream

太过爱你忘了你带给我的痛 2022-01-08 00:29 75阅读 0赞

[Mondriaan's Dream][Mondriaan_s Dream]

有一个\\(n\\times m\\)的网格图，用\\(1\\times 2\\)的矩形网格无重叠的摆满的方案数，\\(1\\leq n,m \\leq 11\\)。

### 解 ###

数据范围已经提示可以二进制压缩，考虑到网格图常以行列为阶段，所以自然想到\\(dp\[i\]\[j\]\\)表示处理到第i行，第i行的状态为j的方案数。

而对于状态j的解释，最自然的是其中1表示一个竖着的网格，但是注意这样并不能保证竖着的矩形长度正好为2,所以设1为此处为矩形的上半，注意到要保证一行的合法性，我们的保证竖着的矩形之间有偶数个网格，而这个我们可以预处理，设\\(a\[i\]\\)表示状态i是否合法，于是我们有

\\\[dp\[i\]\[j\]=\\sum\_\{k=0\}^\{2^m-1\}dp\[i-1\]\[k\](!k\\&j\\&\\&a\[k|j\])\\\]

边界：\\(dp\[1\]\[i\]=1,i=1,2,3,...,2^m-1(a\[i\])\\)

答案：\\(\\sum\_\{i=0\}^\{2^m-1\}dp\[n\]\[i\]\\)

参考代码：

#include <iostream> #include <cstdio> #include <cstring> #define il inline #define ri register #define ll long long using namespace std; ll dp[12][2048]; bool check[2048]; int main(){ int h,w,li; while(scanf("%d%d",&h,&w),h&&w){ li=(1<<w)-1,memset(dp,0,sizeof(dp)); memset(check,0,sizeof(check)); for(ri int i(0),j,k;i<=li;++i){ for(j=k=0;j<w;++j) if(i>>j&1){if(k&1)break;k&=0;} else k^=true; if(j==w&&!k)check[i]|=true,dp[1][i]=1; } for(ri int i(2),j,k;i<=h;++i) for(j=0;j<=li;++j) for(k=0;k<=li;++k) if(!(j&k)&&check[j|k]) dp[i][j]+=dp[i-1][k]; printf("%lld\n",dp[h][0]); } return 0; }

转载于:https://www.cnblogs.com/a1b3c7d9/p/10940234.html

[Mondriaan_s Dream]: http://poj.org/problem?id=2411

发表评论取消回复

表情：

评论列表（有 0 条评论，75人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2411 Mondriaan's Dream【状压DP】

意：给你一个n\*m的矩阵，让你用1\*2的矩形覆盖全部，问你方案数。思路：我们可以发现，每个小矩形有两种放置方式，横着放和竖着放，我们设dp\[i\]\[s\]表示...

怼烎@/ 2024年04月19日 16:32/ 0 赞/ 8 阅读

相关 English Contest -- The Programmer's Dream

Yes, The Programmer’s Dream! How many programmers here? I am sure of that every body he

妖狐艹你老母/ 2022年08月08日 03:30/ 0 赞/ 94 阅读

相关 pku 2411 Mondriaan's Dream dp 状态压缩

以前没做过状态压缩的题目,今天是见识了,我看下下面这段精辟的话才做出来的. -\_- 本该很早就ac的题一直调到现在，why？这次真的是自己的状态很差的原因啊！下午看了一

我会带着你远行/ 2022年07月12日 11:00/ 0 赞/ 111 阅读

相关从GoogLeNet架构到deep dream模型

文章来源： http://blog.csdn.net/diligent\_321/article/details/53292484 虽然深度神经网络在计算机视觉方面

旧城等待，/ 2022年06月06日 03:09/ 0 赞/ 146 阅读

相关 ZOJ - 3211 Dream City (贪心+dp)

思路：增长速度快的只有放在后面砍才能获得最大的收益。 dp\[i\]\[j\]表示从前i棵树中选出j棵树，在前j天砍，砍得顺序就是排序的顺序 include<bi

淡淡的烟草味﹌/ 2022年05月27日 14:14/ 0 赞/ 107 阅读

相关 The Dream of Life——生命之梦

If you awaken from this illusion and you understand that black implies white, self impli

Myth丶恋晨/ 2022年05月23日 13:38/ 0 赞/ 100 阅读

相关 POJ 2411 Mondriaan's Dream（压缩DP）

Mondriaan's Dream <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3

左手的ㄟ右手/ 2022年04月10日 09:38/ 0 赞/ 128 阅读

相关 Mondriaan's Dream

[Mondriaan's Dream][Mondriaan_s Dream] 有一个\\(n\\times m\\)的网格图，用\\(1\\times 2\\)的矩形网格无重

太过爱你忘了你带给我的痛/ 2022年01月08日 00:29/ 0 赞/ 76 阅读

相关 Zju1100 Mondriaan

题目描述有一个m行n列的矩阵，用1\2的骨牌(可横放或竖放)完全覆盖，骨牌不能重叠，有多少种不同的覆盖的方法？你只需要求出覆盖方法总数mod p的值即可。输

谁践踏了优雅/ 2021年12月24日 16:25/ 0 赞/ 100 阅读

相关状压DP POJ 2411 Mondriaan'sDream

[题目传送门][Link 1] 1 / 2 题意：一个hw的矩阵（1<=h,w<=11），只能放12的模块，问完全覆盖的不同放发有多少种？

约定不等于承诺〃/ 2021年12月23日 09:17/ 0 赞/ 173 阅读