poj2411 Mondriaan's Dream--状压dp

原题链接：​​http://poj.org/problem?id=2411​​

.

题意：一个n*m的方格，给定一个1*2的方块，要求用这个方块填充方格，填满，一共多少种填充方法。

分析：对于一行的某一列来说，该列有三种：横着，竖着，不填。首先dfs求出一行可以有多少种可能。再枚举每种可能，直接看代码，不难的。

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>
#include<vector>
#include<cstring>
#include<queue>
#include<stack>
#include<algorithm>
#include<cmath>
#include<string>
#include<stdio.h>
#define INF 99999999
#define eps 0.0001
using namespace std;
 
int w, h;
int num;
long long dp[12][1 << 11];
int path[11 * (1 << 11)][2];

void dfs(int l, int now, int pre)
{
  if (l > w)
    return;
  if (l == w)
  {
    path[num][0] = pre;
    path[num++][1] = now;
    return;
  }

  dfs(l + 2, (now << 2) | 3, (pre << 2) | 3);//横着放
  dfs(l + 1, (now << 1) | 1, pre << 1);//竖着放
  dfs(l + 1, now << 1, (pre << 1) | 1);//不放
}

int main()
{
  while (~scanf("%d%d", &w, &h) && (w || h))
  {
    if (w*h % 2 == 1)
      printf("0\n");
    else
    {
      if (w > h)
        swap(w, h);
      num = 0;
      dfs(0, 0, 0);//记住第一个参数是0，不是1，因为对于最后一列，如果是1，等到了w列，正好退出，只有0才会把w列考虑进去
      memset(dp, 0, sizeof(dp));
      dp[0][(1 << w) - 1] = 1;
      for (int i = 0; i < h; i++)
        for (int j = 0; j < num; j++)
          dp[i + 1][path[j][1]] += dp[i][path[j][0]];
      printf("%lld\n", dp[h][(1 << w) - 1]);
      
    }
  }
  return 0;
}