学步园

给定一个宽和高分别为w和h的矩形，用1*2的小矩形填满，可以有多少种填法。

对于第i行的摆放状态，我们只用考虑上一行的摆放状态。而第i行有多少种摆法，取决于到达此时第i行状态的第i-1行的状态【晕了。。】

即dp[i][now] = ∑dp[i-1][pre]，pre是可到达now的子状态。

对于第i行每个格子放与不放，用01记录，一行格子有(1 << w) - 1种状态，对于第d列：

1.i-1行放竖的，则i-1的d位为1，i的d位为0；

2.i行放竖的，则i-1的d位为0，i的d位为1【和第一种不一样，因为要考虑顺序】；

3.两行都放横的，则两行的d和d+1位都是1.

#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
#define LL long long
#define MAXN (1 << 11) + 10

int h, w, tot;
LL dp[13][MAXN];
int sta[11 * MAXN][2];

void dfs(int d, int now, int pre)
{
    if(d > w)
        return ;
    if(d == w)
    {
        sta[tot][0] = pre;
        sta[tot++][1] = now;
    }

    dfs(d + 1, now << 1 | 1, pre << 1);
    dfs(d + 1, now << 1, pre << 1 | 1);
    dfs(d + 2, now << 2 | 3, pre << 2 | 3);
}

LL work()
{
    tot = 0;
    dfs(0, 0, 0);
    memset(dp, 0, sizeof(dp));
    dp[0][(1 << w) - 1] = 1;
    for(int i = 0; i < h; i++)
        for(int j = 0; j < tot; j++)
            dp[i + 1][sta[j][1]] += dp[i][sta[j][0]];
    return dp[h][(1 << w) - 1];
}

int main()
{
//    freopen("2411.in", "r", stdin);

    while(scanf("%d%d", &h, &w) && h && w)
    {
        if(h < w)
            swap(h, w);
        printf("%I64d\n", work());
    }
    return 0;
}

貌似还有插头dp的写法，需要研究一下。。