Poj 2411 Mondriaan's Dream(状压DP)

2023-12-25 15:48
文章标签 dp poj 状压 dream 2411 mondriaan

本文主要是介绍Poj 2411 Mondriaan's Dream(状压DP),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Mondriaan’s Dream
Time Limit: 3000MS Memory Limit: 65536K
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
题意:用1*2的砖块来覆盖地面的方案数.

/*
状压DP.
f[i][S]表示当前第i行,状态为S.
我们发现每一行状态只和前一行相关.
然后就可以DP辣.
枚举所有可行状态转移.
0 不放/竖着的上面那块
1 横着/竖着的下面那块
强行把竖着的状态给下边那个.
因为必须要填满,
所以状态合不合法就比较好转移了.
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#define MAXN 5001
#define LL long long
using namespace std;
LL f[21][MAXN];
int n,m;
bool pre(int s)
{for(int i=0;i<m;){if(s&(1<<i)){if(i==m-1) return false;if(s&(1<<i+1)) i+=2;else return false;}else i++;}return true;
}
bool check(int s,int ss)
{for(int i=0;i<m;){if(s&(1<<i)){if(ss&(1<<i)){if(i==m-1||!(s&(1<<i+1))||!(ss&(1<<i+1))) return false;else i+=2;}else i++;}else {if(!(ss&(1<<i))) return false;else i++;}}return true;
}
void slove()
{memset(f,0,sizeof f);for(int s=0;s<=(1<<m)-1;s++) if(pre(s)) f[1][s]=1;for(int i=2;i<=n;i++)for(int s=0;s<=(1<<m)-1;s++)for(int ss=0;ss<=(1<<m)-1;ss++)if(check(s,ss)) f[i][s]+=f[i-1][ss];printf("%lld\n",f[n][(1<<m)-1]);
}
int main()
{while(~scanf("%d%d",&n,&m)){if(!n&&!m) break;if(n<m) swap(n,m);slove();}return 0;
}

这篇关于Poj 2411 Mondriaan's Dream(状压DP)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/536058

相关文章

hdu4826(三维DP)

这是一个百度之星的资格赛第四题 题目链接:http://acm.hdu.edu.cn/contests/contest_showproblem.php?pid=1004&cid=500 题意:从左上角的点到右上角的点,每个点只能走一遍,走的方向有三个:向上,向下,向右,求最大值。 咋一看像搜索题,先暴搜,TLE,然后剪枝,还是TLE.然后我就改方法,用DP来做,这题和普通dp相比,多个个向上

hdu1011(背包树形DP)

没有完全理解这题, m个人,攻打一个map,map的入口是1,在攻打某个结点之前要先攻打其他一个结点 dp[i][j]表示m个人攻打以第i个结点为根节点的子树得到的最优解 状态转移dp[i][ j ] = max(dp[i][j], dp[i][k]+dp[t][j-k]),其中t是i结点的子节点 代码如下: #include<iostream>#include<algorithm

hdu4865(概率DP)

题意:已知前一天和今天的天气概率,某天的天气概率和叶子的潮湿程度的概率,n天叶子的湿度,求n天最有可能的天气情况。 思路:概率DP,dp[i][j]表示第i天天气为j的概率,状态转移如下:dp[i][j] = max(dp[i][j, dp[i-1][k]*table2[k][j]*table1[j][col] )  代码如下: #include <stdio.h>#include

usaco 1.1 Broken Necklace(DP)

直接上代码 接触的第一道dp ps.大概的思路就是 先从左往右用一个数组在每个点记下蓝或黑的个数 再从右到左算一遍 最后取出最大的即可 核心语句在于: 如果 str[i] = 'r'  ,   rl[i]=rl[i-1]+1, bl[i]=0 如果 str[i] = 'b' ,  bl[i]=bl[i-1]+1, rl[i]=0 如果 str[i] = 'w',  bl[i]=b

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];