d054: 11310 - DELIVERY DEBACLE
Tags : DP
Accepted rate : 543人/599人 ( 91% ) [非即時]
評分方式:
Tolerant

最近更新 : 2014-11-01 10:53

Content

Wolfgang Puck 有兩個很特別的習慣:

   I.  他只做兩種形狀的蛋糕。一種是面積為一單位的方形,另一種是面積為三單位的 L 形。

   II. 他只用特定尺寸的盒子來裝蛋糕。這些盒子的寛度都是二單位,但各種不同長度都有。

有一天,Wolfgang 想知道有幾種不同的方式可以把蛋糕裝滿一個特定尺寸的盒子。你能幫他嗎?

左圖為蛋糕的尺寸,右圖為裝滿長度 6 的盒子的一種方法。

裝滿長度為 2 的盒子的 5 種方法。.

Input

輸入的開始有一個 t,表示有幾個不同長度的盒子。接下來的 t 行每行有一個整數 n (1 ≤ n ≤ 40)

Output

相對於每個 n 輸出一行,該行中的數字為有幾種方法可以用上述的蛋糕裝滿一個 2×n 的盒子。輸出的數字保證小於1018

Sample Input
2
1
2
Sample Output
1
5
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :
DP
Tags:
DP
出處:
UVa11310 [管理者:
snail (蝸牛)
]


ID User Problem Subject Hit Post Date
17856
ufve0704 (爬 我爬 我爬爬爬 有排行榜這種東西就是...)
d054
公式:
200 2019-05-26 10:31