这题和编程之美上面的“地板覆盖”问题有点像,不同的是,编程之美上面只需要判定能否覆盖,这题需要求出总方案数目
结题报告转自http://duanple.blog.163.com/blog/static/709717672008930104124684/
题意:给你一个h*w的矩形,用一个1*2的小矩形去填充,问有多少种填充方法,不考虑对称性。
关键点提示:
1.DFS部分
实际上是在枚举第i行的放置方法,由此便可以确定出该行及上一行的状态。
对于第i行,状态(参数next_stat)的定义是指,前i-1行完全放满,第i行的所有位置是否放置(0,1表示)组成的二进制序列,转化为十进制数后所代表的状态。
放置方法,总共存在三种,
1. 竖直放置
2. 水平放置
3. 不放置
以竖直放置举例说明:
假设第i行的第3列位置是要竖直放置,则说明它的前一行该列位置必然是0,放置后这一行的状态必然变成了1,所以上一行的状态应该是prev_stat << 1,该行是(next_stat << 1)|1,直到column == w,即从左到右开始枚举,枚举到了最右列,说明该放置方案完毕。
本质上是枚举的第i行的放置方案,而放置方案实际上确定了上下两行的状态。
2.注意到prev_stat并没有明确指明列值,对于列的变化实际上是通过移位来反映的。
prev_stat,next_stat初始均为0,第一次移位确定的是左边第一个位置的状态,这样随着移位的进行这个状态不断的往高位迁移,这样在以后的移位,或运算中保证保持不变。也就是说,随着移位的进行,本来第一位表示的是最左边那列的状态,慢慢得变成第2,3,4,...w位来表示它的状态,实际上是该状态值不断得伴随着移位再向高位迁移。
DFS+DP解法解题报告:
当高度和宽度都为奇数时显然答案为0, 这个用面积的奇偶性就很容易得证
记f[i][s1]为第i-1行全满且第i行状态为s1时的种数,便有如下递推关系:
f[i][s1] = sigma(f[i-1][s2]);
其中(s1, s2)整体作为一个放置方案, 这样f[h+1][0]即是答案了
对于每一个位置,我们有三种放置方法:
1. 竖直放置
2. 水平放置
3. 不放置
d为当前列号 ,初始化d, s1, s2都为0;对应以上三种放置方法,s1, s2的调整为:
1. d = d + 1, s1 << 1 | 1, s2 << 1;
2. d = d + 2, s1 << 2 | 3, s2 << 2 | 3;
3. d = d + 1, s1 << 1, s2 << 1 | 1;
先就第一种情况解释一下,另外的两种情况可以类推
S1<<1|1即为把s1的二进制表示后面加上一个1,对就于本题来说就是(d+1)列上放
置,s2<<1即为把s2的二进制表示后面加上一个0,对于本题来说就是(d+1)列上不放置。
但为什么s1、s2会如此变化呢?本人在此处想了好长时间,后来想明白了,s1对应于本行的状态,s2对应
于上一行的状态,能竖直放置意味着上一行的(d+1)列是空着的,因此此时上一行的状态为s2<<1,同时竖
置放置了之后,则本行(d+1)行放置了东西,状态于是变为s1<<1|1;
当d = w时保存状态
对于初始时的f值,可以假设第0行全满,第一行只有两种放法:
1. 水平放置 d = d + 2, s << 2 | 3;
2. 不放置 d = d + 1, s << 1;
另外,利用滚动数组,可以减少空间的开销
还有一个可以提高较率的地方,当输入的 w > h 时,对调,因为横向的运算是指数
级的, 而列向的是线性的.
分享到:
相关推荐
里面有非常详细的对于POJ 2411的解题报告,相信对于初学动态规划和深度优先搜索的同学来说有很好的帮助作用。
关于poj dp分类,我一直寻找dp的分类,终于找到了,也上传一下
poj 2488——dfs深度优先遍历 //给行数列数,求问能否遍历,给出字典序的一种遍历
Poj 3342 这是一道树状dp题目,题意是这样的,一个公司,每个人有且仅有一个Boss,除了最大的Boss没有Boss(显然),现在要参加一个聚会,要求参加的人数最多,但是棘手的.......
北大POJ3733-Changing Digits【DFS+强剪枝】 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
北大POJ1691-Painting A Board 【拓扑+DFS】 解题报告+AC代码
北大POJ1020-Anniversary Cake 解题报告+AC代码
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
北大POJ3373-Changing Digits【DFS+强剪枝】 解题报告+AC代码
这是一道很不错的题目,dp解决的经典例子,是学习dp,和练习的好题目。。。。
这是黑不来就的poj上的所有dp题目的大型分类 好使好用
北大POJ1015-Jury Compromise【动态规划DP】 解题报告+AC代码
poj训练 c语言poj训练 西工大 poj 100题。
北大POJ2002-Squares 解题报告+AC代码
poj2009离线题库 poj2009离线题库
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
西北工业大学POJ第二季习题,一共15题全部都有,便捷广大西北工业大学大一的孩子。
西工大poj里基本所有的习题了,应该是比较新的习题总集了,1-100.