SGU 131 贴地砖类型 状态压缩DP
用dp[i][j]表示要贴第i层时，第i-1层的状态， 然后每一层dfs枚举一下情况即可
dfs(x, y, pre, now) x层数 y枚举的当前列 pre 前一层状态, now当前层状态


根据当前列y的这位上pre和now状态，确定要贴的图形， 注意贴完以后pre层必须满状态，在贴的过程中处理必须优先把pre层贴满。


状态转移如下图：.表示空，*表示满

#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;#define LL long longint n, m;LL dp[11][1<<9];int f(int a) {return 1<<a;}LL cnt;int N;void dfs(int x, int y, int pre, int now) {if(y >= m) {dp[x+1][now] += cnt;return;}if( pre&f(y) && now&f(y)) {    dfs(x, y+1, pre, now);    return;}if( !(pre&f(y)) && !(now&f(y)) ) {    dfs(x, y+1, pre|f(y), now|f(y)); //*    if(y+1 < m) {                    //*            if( !(now&f(y+1)) )                         //*                dfs(x, y+1, pre|f(y), now|f(y)|f(y+1)); //**            if( !(pre&f(y+1)) )                         //**                dfs(x, y+1, pre|f(y)|f(y+1), now|f(y)); //*            if( !(pre&f(y+1)) && !(now&f(y+1)) )          //**                dfs(x, y+1, pre|f(y)|f(y+1), now|f(y+1)); // *    }    return;}if( pre&f(y) && !(now&f(y)) ) {    if( y+1 < m && !(now&f(y+1)) )                 //*            dfs(x, y+1, pre|f(y), now|f(y)|f(y+1));    //**    if( y+1 < m && !(pre&f(y+1)) && !(now&f(y+1)) )    // *            dfs(x, y+1, pre|f(y+1), now|f(y)|f(y+1));      //**    dfs(x, y+1, pre, now); // 不放    return;}if( !(pre&f(y)) && now&f(y)) {    if(y+1 < m && !(pre&f(y+1) && !(now&f(y+1))) ) //**            dfs(x, y+1, pre|f(y)|f(y+1), now|f(y+1));  // *}}int main() {int i, j;while(~scanf("%d%d", &n, &m)) {N = 1<<m;memset(dp, 0, sizeof(dp));dp[0][N-1] = 1;for(i = 0; i < n; i++)for(j = 0; j < N; j++) if(dp[i][j]) {cnt = dp[i][j];dfs(i, 0, j, 0);}cout << dp[n][N-1] << endl;}}/*2 359 9388961059855222726 65350806*/