UVA 11270 Tiling Dominoes(用1×2骨牌覆盖n×m棋盘,有多少种方法)

传送门:UVA 11270 Tiling Dominoes

题意:用1×2骨牌覆盖n×m棋盘,有多少种方法(n×m<=100)

思路:n×m<=100->min(n,m)<=10
我们按照从上到下,从左到右的顺序呢将棋盘划分成若干个阶段,每个阶段有2^m个节点,其中每个节点用一个m为二进制整数表示

阶段决策是”以当前格子为右下角,要不要放骨牌以及放哪种骨牌”

#include<bits/stdc++.h>
using namespace std;
const int maxn=1<<12;
long long dp[2][maxn];
int cur,n,m;

void add(int a,int b){
    if(b&(1<<m))
        dp[cur][b^(1<<m)]+=dp[cur^1][a];
}

int main(){
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n<m)
            swap(n,m);
        int all=(1<<m)-1;
        memset(dp,0,sizeof(dp));
        dp[0][all]=1;
        cur=0;
        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 sta=0;sta<=all;sta++){
                    if(dp[cur^1][sta]==0)
                        continue;
                    add(sta,sta<<1);//这个点不放,sta<<1让sta的最后一位为0
                    if(i && !(sta & ( 1<<(m-1) ) ) )//竖着放,不是第一行,而且上面的位置没放
                        add(sta,(sta<<1)^(1<<m)^1);
                    if(j && !(sta & 1) )    //横着放
                        add(sta,(sta<<1)^3);
                }
            }
        printf("%lld\n",dp[cur][all]);
    }
    return 0;
}