這一題是插頭DP，而狀態轉移的方式和上一題不太一樣，這裡是「當前狀態」轉移到「後來狀態」，上一題則是「當前狀態」由「之前狀態」轉移過來。
關於插頭DP的說明，請參考此篇:
/*
插頭DP，或輪廓線DP
http://mypaper.pchome.com.tw/zerojudge/post/1325083578
骨牌跟骨牌間的空隙即是有插頭的地方。
考慮放直立的骨牌的話，則上方必為空格。
考慮放橫躺的骨牌的話，則左方必為空格，而上方必不為空格，否則不能填滿。
考慮不放的話，則上方必不為空格，否則不能填滿。
*/
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
int n, m;
while(scanf("%d %d", &n, &m) == 2)
{
if(n < m) swap(n, m);
long long int dp[2][1 << 10] = {}; //滾動陣列
int now = 0, pre = 1;
int ALL = (1<<m)-1;
dp[now][ALL] = 1;
for(int i = 0; i < n; i ++)
{
for(int j = 0; j < m; j ++)
{
swap(now, pre);
memset(dp[now], 0, sizeof(dp[now]));
for(int k = 0; k <= ALL; k ++)
{
int left, up;
/*
這題中，輪廓線右、下插頭的狀況一樣，
要嘛就都有，不然就都沒有，
所以用位元表示時，直接省略輪廓線直的那條線。
│
│
一一
*/
if(j == 0) left = 1;
else left = k&(1<<(j-1));
up = k&(1<<j);
if(up == 0) //放直立的骨牌
{
dp[now][k^(1<<j)] += dp[pre][k];
}
if(up != 0 && left == 0) //放橫躺的骨牌
{
dp[now][k^(1<<(j-1))] += dp[pre][k];
}
if(up != 0) //不放，留空格
{
dp[now][k^(1<<j)] += dp[pre][k];
}
}
}
}
printf("%lld\n", dp[now][ALL]);
}
return 0;
}
天邊。世界 