跳转到手机网站,苏州网站营销公司,公众号开发者id在哪,openwrt wordpress1. 题目 diamonds 题目描述 小keke同学非常喜欢玩俄罗斯方块#xff08;*^*#xff09;,他最近发现传统的俄罗斯方块很无趣#xff0c;于是他想到了一个新规则的游戏来恶心你#xff08;……#xff0c;没素质啊#xff09;。 游戏是这样的#xff1a; 给定你一个宽度为…1. 题目 diamonds 题目描述 小keke同学非常喜欢玩俄罗斯方块*^*,他最近发现传统的俄罗斯方块很无趣于是他想到了一个新规则的游戏来恶心你……没素质啊。 游戏是这样的 给定你一个宽度为w的游戏场地我们设高度为正无穷。现在给你3种俄罗斯方块 1*2的方块 2*2的方块 2*2的方块去掉一个1*1的方块 如果你明白俄罗斯方块的规则的话方块在下落过程中是可以随便旋转的。而且是从上往下落上面的落在下面的上面废话 现在给定你一个高度h让你求出有多少种游戏的方法使得最后恰好落满h的高度最上层是齐平的。因为这样可以得巨多分巨舒服~~~~~ 输入文件(diamonds.in) 两个整数h,w含义如题所述 输出文件(diamonds.out) 一个整数为能达到要求的游戏方法的总数。 数据范围 1h,w9,注意答案有可能很大你懂得用不到高精度 样例输入 2 2 样例输出 3 2. 题目实质 用给定的三种砖讲一个区域铺满又是废话 3. 算法 DPDFS (也就是状态压缩型 DP ) 首先每一个状态均可以由他前面的某一个状态转移而来所以满足 DP 的无后效性用 DP 解决。 方程十分好写f[I,j]:sigma(f[I-1,k]*g[k,j]其中状态 k 可以转移到状态 j I 表示该状态铺满的高度为高度为 I ) 初始值 f[1,0]:1; 因为本题中一共三种砖所以情况会很多这也是比较恶心人的地方因为情况太多有多种转移的方法所以不能用 Boolean 类型数组直接判断而应该用一个 g 数组记录然后用乘法原理将方案数直接进行累加。 状态用二进制HASH存储。 将矩阵的行看成一种状态则某一行矩阵的铺砖情况可以用一个串表示表示未铺砖表示已铺了砖。 然后状态改变时用位运算改变。 对于上下两行要能用某种类型的砖铺必须该砖所覆盖的区域为空。 当搜出边界时直接跳出。递归出口 4. 注意事项 一定要开 int64 5. 程序代码 Leve pascal var n,m,i,j,k:longint; f:array[0..9,0..1024] of int64; g:array[0..1024,0..1024] of int64; procedure dfs(step,now:longint); begin if stepm1 then begin inc(g[i,now]); exit; end; if 10 then dfs(step1,now) //如果这一行不能再铺了就搜下一行。 else begin if (11) then dfs(step1,now1 转载于:https://www.cnblogs.com/SueMiller/archive/2011/08/10/2133801.html
