题解 UVA11270 【Tiling Dominoes】

· · 题解

考虑轮廓线DP。

对于一个格子来说，有4种情况。

  1. 上面没有格子，左面没有格子。这种情况必须向上填。
  2. 上面没有格子，左边有格子。同上。
  3. 上面有格子，左面没有格子。可以向左面填，也可以不填。
  4. 上面有格子，左面有格子。必须不填。

这里的二进制数表示的是该行到此格子的前一个及此格子的上一个格子到上一行结束的填充方案。

不用记忆化啊

#include<cstdio>
#include<cstring>
typedef long long LL;
int n,m,opt,fal,_2[14];
LL f[2][2100];
int main(){
    _2[0]=1;
    for(int i=1;i<14;i++)_2[i]=_2[i-1]<<1;
    while(scanf("%d%d",&n,&m)!=EOF){
        if(n*m%2==1){
            puts("0");
            continue;
        }
        memset(f,0,sizeof(f));
        if(n<m)opt=n,n=m,m=opt;
        opt=0;
        fal=(1<<m)-1;
        f[0][fal]=1;
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            opt^=1;
            memset(f[opt],0,sizeof(f[opt]));
            for(int k=0;k<=fal;k++){
                if(!(k&_2[j]))f[opt][k|_2[j]]+=f[opt^1][k];
                //上面没格子，必须填上面
                if(j&&(k&_2[j])&&!(k&_2[j-1]))f[opt][k|_2[j-1]]+=f[opt^1][k];
                //上面有格子，左面没有，可以填左边
                if(k&_2[j])f[opt][k^_2[j]]+=f[opt^1][k];
                //上面有格子，左边没有，可以不填
                //上面有格子，左面有，必须不填
                //这两种情况用一种转移
            }
        }
        printf("%lld\n",f[opt][fal]);
    }
}