题目大意：求 2 * 1 骨牌覆盖 h * w 棋盘的方案数。
轮廓线动态规划。逐格转移，记状态 f[i, j, k] 为处理至第 (i, j) 格（设 0 ≤ i < h，0 ≤ j < w），前 w 格的覆盖状态为 k 的方案数，记 0 为已覆盖，1 为未覆盖，利用二进制状态压缩，则 k 二进制下从低位向高位第 l 位表示当前格前第 l 格是否覆盖的状态，可知 k 最多只需记 w 位即可。对于当前状态 k，转移分为以下三种情况：
当前列不为最左列（即 j > 0），此时若格 (i, j - 1) 未覆盖（即 k and 1 = 1），且格 (i - 1, j) 已覆盖（即 k and 2w−1 = 0），则可以覆盖格 (i, j - 1) 和格 (i, j)，即状态 f[i, j - 1, k] 可以转移到状态 f[i, j, (k - 1) * 2]。
若格 (i - 1, j) 已覆盖（即 k and 2w−1 = 0），则可以不覆盖当前格 (i, j)，即状态 f[i, j - 1, k] （若 j = 0 则为状态 f[i - 1, w - 1, k]） 可以转移到状态 f[i, j, k * 2 xor 1]。
当前行不为最上行（即 i > 0）（实际代码中可以不用判断），此时若格 (i - 1, j) 未覆盖（即 k and 2w−1 = 1），则可以覆盖格 (i - 1, j) 和格 (i, j)，即状态 f[i, j - 1, k] （或状态 f[i - 1, w - 1, k]） 可以转移到状态 f[i, j, k * 2 xor 2w ]。
设初始状态 f[-1, w - 1, 0] = 1，f[-1, w - 1, 1 .. 2w−1 ] = 0，转移相当于方案数求和，则状态 f[h - 1, w - 1, 0] 即为答案。可以采用滚动数组优化，降低空间复杂度和编程复杂度。由于答案过大，故需用到超长整型保存答案。
代码如下：
#include<iostream> #include<stdio.h> using namespace std; long long f[2][2055]; int main() { int cur,h,w; while(true) { scanf("%d %d",&h,&w); if(h==0&&w==0) break; cur=0; for(int i=0;i<1<<w;i++) f[0][i]=f[1][i]=0; f[cur][0]=1; for(int i=0;i<h;i++) for(int j=0;j<w;j++) { if(j>0) for(int k=1;k<1<<w-1;k+=2) f[cur^1][k-1<<1]+=f[cur][k]; for(int k=0;k<1<<w-1;k++) f[cur^1][k<<1^1]+=f[cur][k],f[cur][k]=0, f[cur^1][k<<1]+=f[cur][k^1<<w-1],f[cur][k^1<<w-1]=0; cur^=1; } cout<<f[cur][0]<<endl; } return 0; }事实上，2 * 1 骨牌覆盖 n * m 棋盘的方案数有公式：1
f(n,m)={∏⌊n/2⌋i=1∏⌊m/2⌋j=1[4cos2(i∗πn+1)+4cos2(j∗πm+1)]0if n is even, or m is even.if n is odd, and m is odd. 直接利用公式计算时需注意精度。代码如下： #include<iostream> #include<math.h> #include<stdio.h> using namespace std; #define PI (3.1415926535897932) int main() { int h,w;double ans; while(true) { scanf("%d %d",&h,&w); if(h==0&&w==0) break; ans=!((h&1)&(w&1)); for(int i=1;i<<1<=h;i++) for(int j=1;j<<1<=w;j++) ans*=4*pow(cos(i*PI/(h+1)),2)+4*pow(cos(j*PI/(w+1)),2); cout<<(long long)(ans+0.5)<<endl; } return 0; }