d389: 11069 - A Graph Problem
Tags :
Accepted rate : 257人/267人 ( 96% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-09-14 15:17

Content

給一個有 n ( 1 <= n <= 76 )個節點的無向圖形(圖形如下

你的任務是:給你 n ,請算出這個圖形有以下性質的節點子集合共有多少個。

  • 集合裡不能有兩個相鄰的點。例如圖形中有n=3個節點,則集合 {1,2} 是違法的,而集合 {1,3} 是合法的。
  • 當這個集合能再加入任一節點,卻可以不和其它節點相鄰,則這個集合是違法的。例如圖形中有n=5個節點,則集合 {1,5} 是違法的,因為這個集合再加入節點3仍不和其它節點相鄰,而集合 {1,3,5} 則是合法的。

所以,當圖形有 n=5 個節點時,應該有 4 個合法的集合:{1,3,5},{2,4},{2,5},{1,4}.

Input

測試資料中有很多個測資

每個測資一列

每列包含一個數字 n (1 <= n <= 76)

請用EOF來判斷檔案結束

Output

請輸出一列含有上述性質的子集合的數目

答案不會超過 231

Sample Input
1
2
3
4
5
30
Sample Output
1
2
2
3
4
4410
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
Hint :

* 中文翻譯:Lucky 貓 

DP (遞迴)

Tags:
出處:
UVa11069 [管理者:
morris1028 (碼畜)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」