[TIOJ 1452] 巧拼放置問題

作法：

位元DP的經典題設 dp[ i ][ j ] 代表在第 i 排，然後 j 的每個 bit 代表這格有沒有被骨牌覆蓋，並且前 i-1 排都是撲滿的，他的方法數。然後轉移的時候用 DFS 轉移。例如現在這排是：
111000101
並且前面幾排都滿的，那麼第一個 1 有兩種可能，他連他上面的，或是他連他右邊的，就這樣往右DFS決定每個凸出來的部分的放法，就可以轉移回 dp[ i-1 ][ j ' ] 了。

code :

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int maxn=15 ;
 
LL dp[maxn][1<<maxn] ;
int n,m ;
 
LL dfs(int now,int S,int col,int x)
{
    if(x==m) return dp[col-1][now] ;
    if(!(S&(1<<x))) return dfs(now,S,col,x+1) ;
    LL ret=dfs(now^(1<<x),S,col,x+1) ;
    if(S&(1<<(x+1))) ret+=dfs(now,S,col,x+2) ;
    return ret ;
}
 
main()
{
    while(scanf("%d%d",&n,&m)==2 && n+m)
    {
        fill(dp[0],dp[0]+(1<<m),0) ;
        dp[0][(1<<m)-1]=1 ;
        for(int i=1;i<=n;i++) for(int j=0;j<(1<<m);j++)
            dp[i][j]=dfs((1<<m)-1,j,i,0) ;
        printf("%lld\n",dp[n][(1<<m)-1]) ;
    }
}