poj 2411 Mondriaans Dream 輪廓線dp

題目意思：   給一個n*m的矩形區域，將1*2和2*1的小矩形填滿方格，問一共有多少種填法。   解題思路：   用輪廓線可以過。   對每一個格子，枚舉上一個格子的狀態，得到當前格子的所有狀態值。   dp[cur][s]表示當前格子的輪廓線狀態為s的情況下的總數   代碼：

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
using namespace std;

/*
freopen("data.in","r",stdin);
freopen("data.out","w",stdout);
*/
ll dp[2][1<<15]; //dp[cur][s]表示當前格子的輪廓線狀態為s的情況下的總數
int n,m,cur;

void update(int a,int b)
{
   if(b&(1<<m)) //將前一個格子的最高位，如果是1,則置零，並更新
      dp[cur][b^(1<<m)]+=dp[1-cur][a];
}
int main()
{
   while(scanf("%d%d",&n,&m)&&m+n)
   {
      //if(m+n)
      if(m>n)
         swap(n,m);
      memset(dp,0,sizeof(dp));
      dp[0][(1<<m)-1]=1; //第一行只能橫著放，把這個狀態初始化為1
      cur=0;
      int lim=1<<m;

      for(int i=0;i<n;i++)
         for(int j=0;j<m;j++) //對每個格子，從前面一個格子推過來
         {
            cur^=1;
            memset(dp[cur],0,sizeof(dp[cur]));
            for(int k=0;k<lim;k++) //枚舉前一個格子的所有狀態
            {
               update(k,k<<1); //不放
               if(i&&!(k&(1<<(m-1))))//豎著放
                  update(k,(k<<1)^(1<<m)^1); //將放著的兩點置1
               if(j&&!(k&1))
                  update(k,(k<<1)^3); //橫著放
            }
         }
      printf("%lld\n",dp[cur][lim-1]);
   }
   return 0;
}