地址：

题意：用1*2和2*1的小长方形铺垫4*W的方格有多少种方法。

mark：这题真是一个非常有意思的题目，第一眼看，觉得应该是很简单的递推题，但是又秒不掉，灰常让人捉集。

首先递推总是想着从后往前由已知解来推出新解。这题很容易想到当W为n的时候，用n-1的结果加上两个竖杠和n-2的结果加上题目分析的那五种中不和n-1重复的4种情况来构造。但是但是但是，这是不完全的。在推导W=3的情况时发现只有9种，然而按题目应该是11种。想了很久才发现漏掉了以下这种情况（由于对称，因此少2种）：

-- -- --|     |  | -- --   |     |  | -- -- --|  |     |    -- --|  |     | -- -- --

 

推至此处，思维已经开始有些混乱了。理了一下。当W=n时，从后往前应该能找到一个不可被分割的最小长度尾部。

例如以下图形，尾部10格图形不可以从中间被分割开来。

-- -- -- -- -- -- -- -- -- -- -- --|  |  |     |     |     |     |     |       -- -- -- -- -- -- -- -- -- --|  |  |  |     |     |     |     |  | -- --    -- -- -- -- -- -- -- --   |  |  |  |     |     |     |     |  |       -- -- -- -- -- -- -- -- -- --|  |  |     |     |     |     |     | -- -- -- -- -- -- -- -- -- -- -- --

假设p[n]表示4*n的不可分割的图形的种类数，容易推得

p[n] = {1,4,2,3,2,3,2,3...}。

至此已经可以拍代码了。不过这里还可以继续化简一下，最后可得dp[n] = dp[n-1]+5dp[n-2]+dp[n-3]-dp[n-4]。

代码：

1 # include 
     
       2  3  4 int dp[25] = {
   1,1,5,11} ; 5  6  7 int main () 8 { 9     int T, i, nCase = 1, n;10     for(i = 4 ; i <= 22 ; i++)11         dp[i] = dp[i-1]+dp[i-2]*5+dp[i-3]-dp[i-4] ;12     scanf ("%d", &T) ;13     while (T--)14     {15         scanf ("%d", &n) ;16         printf ("%d %d\n", nCase++, dp[n]) ;17     }18     return 0 ;19 }