正文 

当前位置： 首页 > java > java框架

poj2411mondriaan'sdream（状压dp）

小胡子Haso      2022-02-06     5

关键词：

【POJ 2411】Mondriaan‘s Dream（状压dp）

Time Limit: 3000MS   Memory Limit: 65536K
Total Submissions: 14107   Accepted: 8152

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

Source

Ulm Local 2000

一个比较明显的状压。给出容器size w*h 又固定了砖块大小1*2 砖块只有两种状态 一种横放一种竖放

设每个1x1的格子放为1未放为0 这样第i行放置状态只与i-1行有关 如果当前未知i-1行为0 那么i行一定要放 既该砖块竖放在i-1和i两行间

这样通过状压后从上往下一行行推 每次枚举状态 模拟判断是否合法即可 最后答案就是dp[w][h]（因为最后一行必须铺满


代码如下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

LL dp[2][1<<11];
int h,w;

bool cal(int pre,int now)
{
	int cnt = 0;
	for(int i = 0; i < h; ++i)
	{
		if(!(pre&1))
		{
			if(!(now&1)) return false;
			if(cnt&1) return false;
			cnt = 0;
		}
		else
		{
			if(!(now&1))
			{
				if(cnt&1) return false;
				cnt = 0;
			}else cnt++;
		}
		pre >>= 1;
		now >>= 1;
	}
	return !(cnt%2);
}

bool can(int sit)
{
	int cnt = 0;
	while(sit)
	{
		if(sit&1) cnt++;
		else 
		{
			if(cnt&1) return false;
			cnt = 0;
		}

		sit >>= 1;
	}
	if(cnt&1) return false;
	return true;
}

int main()
{
	//fread();
	//fwrite();

	while(~scanf("%d%d",&h,&w) && (h+w))
	{
		if(h > w) swap(h,w);
		int tot = 1<<h;
		for(int i = 0; i < tot; ++i)
			dp[0][i] = can(i);
		
		int pos = 1;
		for(int i = 1; i < w; ++i, pos ^= 1)
		{
			memset(dp[pos],0,sizeof(dp[pos]));
			for(int j = 0; j < tot; ++j)
				for(int k = 0; k < tot; ++k)
					if(cal(j,k,h)) dp[pos][k] += dp[pos^1][j];
		}
		
		printf("%lld
",dp[pos^1][tot-1]);
	}

	return 0;
}

然而会发现这种特别暴力的方法灰常灰常慢，多亏出题人良心，比较卡边过。。2000+ms

之后看讨论版许多用位运算做的，由于第i行只与第i-1行相关，i-1行为0的地方i行必须为1 i-1行为1的地方i行不限制

这样枚举第i-1行状态，对于每个状态j ~j&(1<<h)就是i行必放的状态（~j将j取反 1变0 0变1 之后与1<<h且运算 抛去超出状态的位

之后再通过搜索 在可进行选择的位置进行枚举判断 看能不能放横砖（不可放竖砖 因为对于第i行 放竖砖是对于i-1行而言 就是是竖放在i-1与i行之间 跟i+1行无关，在枚举i行状态时 进行刚才的取反和且运算才会出现竖放在i和i+1行间的砖


这样会减去对很多没有必要的状态的枚举 神剪枝！！！Orz


代码如下：

#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

LL dp[2][1<<11];
LL add;
int h,w;

void cal(int id,int pos,int now)
{
	if(pos == h) 
	{
		dp[id][now] += add;
		return;
	}
	cal(id,pos+1,now);
	if(pos <= h-2 && ((now^(1<<pos))&(1<<pos)) && ((now^(1<<(pos+1)))&(1<<(pos+1)))) cal(id,pos+2,now|(1<<pos)|(1<<(pos+1)));
}

int main()
{
	//fread();
	//fwrite();

	while(~scanf("%d%d",&h,&w) && (h+w))
	{
		memset(dp[0],0,sizeof(dp));
		add = 1;
		cal(0,0,0);

		int pos = 1;
		int tot = 1<<h;
		for(int i = 1; i < w; ++i, pos ^= 1)
		{
			memset(dp[pos],0,sizeof(dp[pos]));
			for(int j = 0; j < tot; ++j)
				if(dp[pos^1][j])
				{
					add = dp[pos^1][j];
					cal(pos,0,~j&(tot-1));
				}
		}
		
		printf("%lld
",dp[pos^1][tot-1]);
	}

	return 0;
}















poj2411mondriaan'sdream

DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthedrawingsinhis‘toiletseries‘(wherehehadtousehistoiletpapertodrawon,forallofhispaperwasfilledwithsqu 查看详情

poj2411mondriaan'sdream

题目：SquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthedrawingsinhis‘toiletseries‘(wherehehadtousehistoiletpapertodrawon,forallofhispaperwasfilledwithsquaresandr 查看详情

poj2411mondriaan'sdream

题目链接：http://poj.org/problem?id=2411状态压缩DynamicProgramming.Foreachrow,atithposition,1meansthatthereisablockplacedatthisrowandnextrow(vertically).otherwise,its0.Fortheexampleinquestion,thestateofForthee 查看详情

poj2411mondriaan'sdream

http://poj.org/problem?id=2411 (题目链接)题意　　一个$n*m$的网格，用$1*2$的方块填满有多少种方案。Solution　　轮廓线dp板子。按格dp，对上方和左方的格子的占用情况进行讨论转移。0表示已放置，1表示未放置。细节　　LL，滚动... 查看详情

poj2411mondriaan'sdream状压dp(代码片段)

Mondriaan‘sDreamTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 20822 Accepted: 11732DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.On 查看详情

poj2411mondriaan'sdream

                                 &n 查看详情

[poj2411]mondriaan'sdream（状压dp）（插头dp）

Mondriaan‘sDreamTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 18096 Accepted: 10357Description SquaresandrectanglesfascinatedthefamousDutchpainterPietMondri 查看详情

poj2411mondriaan'sdream--状压dp

题目：Mondriaan‘sDream链接：http://poj.org/problem?id=2411题意：用1*2的瓷砖去填n*m的地板，问有多少种填法。思路：　　很久很久以前便做过的一道题目，状压DP，当时写得估计挺艰辛的，今天搜插头DP又搜到它，就先用状压DP写了下，... 查看详情

[poj2411]mondriaan'sdream状态压缩dp

题意　　给定一个n*m的矩形．　　问有多少种多米诺骨牌覆盖．　　n,m<=11. 实现1#include<cstdio>2#include<cstring>3#include<cstdlib>4#include<cctype>5#defineF(i,a,b)for(registerinti=(a);i<=(b);i++)6#de 查看详情

（hiho1048）poj2411mondriaan'sdream（dp+状态压缩or轮廓dp）

 问题：SquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthedrawingsinhis‘toiletseries‘(wherehehadtousehistoiletpapertodrawon,forallofhispaperwasfilledwithsquar 查看详情

poj2411mondriaan'sdream骨牌铺放状压dp

题目链接题意用(1 imes2)的骨牌铺满(H imesW(H,Wleq11))的网格，问方案数。思路参考focus_best.竖着的骨牌用(egin{pmatrix}0\1end{pmatrix})表示，横着的骨牌用(egin{pmatrix}1&1end{pmatrix})表示。则对于第(i)行，与之相容的第(i-1)行的状态需满足... 查看详情

poj2411mondriaan'sdream——状压dp插头dp

【题目分析】  用1*2的牌铺满n*m的格子。  刚开始用到动规想写一个n*m*2^m，写了半天才知道会有重复的情况。   SoSad。  然后想到数据范围这么小，爆搜好了。于是把每一种状态对应的转移都搜了... 查看详情

poj2411mondriaan'sdream(状压dp)

题意：给出一个n*m的棋盘，及一个小的矩形1*2，问用这个小的矩形将这个大的棋盘覆盖有多少种方法。析：对第（i，j）位置，要么不放，要么竖着放，要么横着放，如果竖着放，我们记第（i，j）位置为0，（i+1，j）为1，如果... 查看详情

[pojp2411]mondriaan'sdream

[pojP2411]Mondriaan‘sDreamTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 18023 Accepted: 10327DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMo 查看详情

poj2411状压dp经典

Mondriaan‘sDreamTimeLimit:3000MS MemoryLimit:65536KTotalSubmissions:16771 Accepted:9683DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.Onenight,afterproducingthed 查看详情

poj.2411.mondriaan'sdream(轮廓线dp)(代码片段)

一道好水的题...还是写篇博客吧...（我以为轮廓线DP入门要做两三个题，结果。。）题目链接题意：求用(1*2)的矩形完全覆盖(n*m)的棋盘的方案数。轮廓线DP入门。另外可以DFS预处理哪些状态能转移到哪些状态，就不用每次(2^m)枚... 查看详情

poj2411(summertrainingday02-i状态压缩dp)

Mondriaan‘sDreamTimeLimit: 3000MS MemoryLimit: 65536KTotalSubmissions: 17187 Accepted: 9911DescriptionSquaresandrectanglesfascinatedthefamousDutchpainterPietMondriaan.One 查看详情

轮廓线dppoj2411-mondriaan'sdream

今天美国的院士过来讲课XD以为会很无聊但是谜之好听，而且英语基本上都听懂了的样子?(´▽｀)逃到图书馆来写解题报告【题目大意】给出一个m*n的方格，用2*1的骨牌覆盖有几种情况。【思路】最基础的轮廓线DP。分为三种... 查看详情