d389. 11069 - A Graph Problem
標籤 : DP
通過比率 : 473人/491人 ( 96% ) [非即時]
評分方式:
Tolerant

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

內容

給一個有 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}.

輸入說明

測試資料中有很多個測資

每個測資一列

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

請用EOF來判斷檔案結束

輸出說明

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

答案不會超過 231

範例輸入 #1
1
2
3
4
5
30
範例輸出 #1
1
2
2
3
4
4410
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1K
提示 :

* 中文翻譯:Lucky 貓 

DP (遞迴)

標籤:
DP
出處:
UVa11069 [管理者: morris1028 (碼畜) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
28701 410446529@gm ... (Yinya1337) d389
513 2021-12-29 00:00
25216 daniel0803 (yoru) d389
分享一下解法
700 2021-04-30 16:28