解题报告 Diamonds
1. 题目
diamonds
题目描述
小keke同学非常喜欢玩俄罗斯方块（*^*）,他最近发现传统的俄罗斯方块很无趣，于是他想到了一个新规则的游戏来恶心你（……，没素质啊）。
游戏是这样的：
给定你一个宽度为w的游戏场地，我们设高度为正无穷。现在给你3种俄罗斯方块：
1*2的方块
2*2的方块
2*2的方块去掉一个1*1的方块
如果你明白俄罗斯方块的规则的话，方块在下落过程中是可以随便旋转的。而且是从上往下落，上面的落在下面的上面（废话！！！）
现在给定你一个高度h，让你求出有多少种游戏的方法，使得最后恰好落满h的高度（最上层是齐平的）。因为这样可以得巨多分！巨！舒服~~~~~
输入文件(diamonds.in)
两个整数h,w含义如题所述
输出文件(diamonds.out)
一个整数，为能达到要求的游戏方法的总数。
数据范围
1<=h,w<=9,注意答案有可能很大（你懂得，用不到高精度）
样例输入
2 2
样例输出
3
2. 题目实质
用给定的三种砖讲一个区域铺满（又是废话）
3. 算法
DP+DFS (也就是状态压缩型 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 step=m+1 then
begin
inc(g[i,now]);
exit;
end;
if 1<<(step-1) and i<>0 then dfs(step+1,now)
//如果这一行不能再铺了，就搜下一行。
else
begin
if (1<1) then
dfs(step+1,now+1<<(step-1)+1<<(step-2));
end;
//铺 2*2-1*1
end;
end;
begin
assign(input,'diamonds.in');
assign(output,'diamonds.out');
reset(input);
rewrite(output);
readln(n,m);
for i:=0 to 1<