題目大意: 給定一個n*m的方格矩形，求用1*2的小矩形完全覆蓋的方案數，n <= 11,m <= 11.
解題思路： 挺經典的一類狀態DP--子矩形覆蓋父矩形，這類DP一般對一行的01狀態進行壓縮，然後按行進行轉移。
這題中每列的0表示未被覆蓋，下一行的就必須覆蓋它，我是理解成一個插頭，留給下一行一個插頭。每列的1表示已被覆蓋，或者理解成沒有向下的插頭。因為當前行只會受上一行影響，所以可以一行一行進行轉移，如果前一個狀態能到下一個狀態，那麼就能轉移。
設dp[i][j]表示到第i行狀態為j的方案數，那麼dp[i][j] += dp[i][k] (if (Ok(j->k))).問題就變成Ok函數怎麼寫呢？易知0->1（上一行為0，當前行為1）,那麼1->?1->0肯定可以，上面無插頭，下面留一個插頭。1->1呢？不能單獨判，必須判下一列是不是也是1->1，不是則不Ok。其實最早我不是這樣寫的，最早的寫法很好理解，如果上一行為0那麼當前行必須為1，如果有一排的1，那麼當前行也必須有0*2或1*2或2*2個1與之對應，2個1必須連續，不過這樣寫跑了1000ms，而用現在這個Ok則跑了200ms。
本題還有一個剪枝，當i * j為奇數的時候方案數為0，因為子矩形的方格數為2是偶數，沒辦法組成一個奇數。
還有我的寫法是從0行開始轉移的，這樣可以if(dp[i][j]) xxxxoooo進行剪枝
測試數據：
[cpp]
f[1][1] = 0;
f[1][2] = 1;
f[1][3] = 0;
f[1][4] = 1;
f[1][5] = 0;
f[1][6] = 1;
f[1][7] = 0;
f[1][8] = 1;
f[1][9] = 0;
f[1][10] = 1;
f[1][11] = 0;
f[2][1] = 1;
f[2][2] = 2;
f[2][3] = 3;
f[2][4] = 5;
f[2][5] = 8;
f[2][6] = 13;
f[2][7] = 21;
f[2][8] = 34;
f[2][9] = 55;
f[2][10] = 89;
f[2][11] = 144;
f[3][1] = 0;
f[3][2] = 3;
f[3][3] = 0;
f[3][4] = 11;
f[3][5] = 0;
f[3][6] = 41;
f[3][7] = 0;
f[3][8] = 153;
f[3][9] = 0;
f[3][10] = 571;
f[3][11] = 0;
f[4][1] = 1;
f[4][2] = 5;
f[4][3] = 11;
f[4][4] = 36;
f[4][5] = 95;
f[4][6] = 281;
f[4][7] = 781;
f[4][8] = 2245;
f[4][9] = 6336;
f[4][10] = 18061;
f[4][11] = 51205;
f[5][1] = 0;
f[5][2] = 8;
f[5][3] = 0;
f[5][4] = 95;
f[5][5] = 0;
f[5][6] = 1183;
f[5][7] = 0;
f[5][8] = 14824;
f[5][9] = 0;
f[5][10] = 185921;
f[5][11] = 0;
f[6][1] = 1;
f[6][2] = 13;
f[6][3] = 41;
f[6][4] = 281;
f[6][5] = 1183;
f[6][6] = 6728;
f[6][7] = 31529;
f[6][8] = 167089;
f[6][9] = 817991;
f[6][10] = 4213133;
f[6][11] = 21001799;
f[7][1] = 0;
f[7][2] = 21;
f[7][3] = 0;
f[7][4] = 781;
f[7][5] = 0;
f[7][6] = 31529;
f[7][7] = 0;
f[7][8] = 1292697;
f[7][9] = 0;
f[7][10] = 53175517;
f[7][11] = 0;
f[8][1] = 1;
f[8][2] = 34;
f[8][3] = 153;
f[8][4] = 2245;
f[8][5] = 14824;
f[8][6] = 167089;
f[8][7] = 1292697;
f[8][8] = 12988816;
f[8][9] = 108435745;
f[8][10] = 1031151241;
f[8][11] = 8940739824;
f[9][1] = 0;
f[9][2] = 55;
f[9][3] = 0;
f[9][4] = 6336;
f[9][5] = 0;
f[9][6] = 817991;
f[9][7] = 0;
f[9][8] = 108435745;
f[9][9] = 0;
f[9][10] = 14479521761;
f[9][11] = 0;
f[10][1] = 1;
f[10][2] = 89;
f[10][3] = 571;
f[10][4] = 18061;
f[10][5] = 185921;
f[10][6] = 4213133;
f[10][7] = 53175517;
f[10][8] = 1031151241;
f[10][9] = 14479521761;
f[10][10] = 258584046368;
f[10][11] = 3852472573499;
f[11][1] = 0;
f[11][2] = 144;
f[11][3] = 0;
f[11][4] = 51205;
f[11][5] = 0;
f[11][6] = 21001799;
f[11][7] = 0;
f[11][8] = 8940739824;
f[11][9] = 0;
f[11][10] = 3852472573499;
f[11][11] = 0;
代碼：
[cpp]
#include <stdio.h>
#include <string.h>
#define MAX (1<<11)
long long dp[20][MAX];
int n,m,ha[20],hb[20];
int Ok(int pre,int cur) {
for (int i = 0; i < m; ++i) {
int t1 = pre & (1<<i);
int t2 = cur & (1<<i);
if (!t1 && !t2) return 0;
if (t1 && t2) {
i++;
if (i == m) return 0;
if ((pre&(1<<i)) == 0) return 0;
if ((cur&(1<<i)) == 0) return 0;
}
}
return 1;
}
int main()
{
int i,j,k,bigest;
while (scanf("%d%d",&n,&m),n + m) {
if (m > n) k = m,m = n,n = k;
if (n % 2 && m % 2) {
printf("0\n");
continue;
}
memset(dp,0,sizeof(dp));
bigest = (1<<m) - 1;
dp[0][bigest] = 1;
for (i = 0; i < n; ++i)
for (j = 0; j <= bigest; ++j)
if (dp[i][j]) for (k = 0; k <= bigest; ++k)
if (Ok(j,k)) dp[i+1][k] += dp[i][j];
printf("%lld\n",dp[n][bigest]);
}
}
