e104. P-6-20. Hyper-cube path - 花中程式設計挑戰系統

Content

一個維度為 n 的 hypercube 是由 2^n 個節點組成的網路，每個節點被賦予唯一一個 0~2^n -1 的編號，對於任兩個節點 i 與 j，他們之間會有邊相連若且惟若 i 與 j 的二進位編碼恰好相差一個位元，我們對於每個節點 i 給予一個正整數的權重 w(i)，請找出編號 0 到編號 2^n -1 的一條最短路徑，使得該路徑所經過的點權重總合(包含起點與終點)為最大。

Time limit: 1 秒

Input

第一行是正整數 n，第二行則是這 2^n 個節點的正整數權重 w(0),w(1),…,w(2^n -1)，數字之間皆以一個空白間隔，其中 n<20 而每個權重值為非負整數不超過 100。

Output

最大權重總和。

Sample Input

範例一：
2
1 2 3 4

範例二：
3
1 2 3 4 5 6 7 8

Sample Output

範例一：
8

範例二：
21

測資資訊：

記憶體限制： 64 MB
公開測資點#0 (20%): 1.0s , <1M
公開測資點#1 (20%): 1.0s , <1M
公開測資點#2 (20%): 1.0s , <1M
公開測資點#3 (20%): 1.0s , <1M
公開測資點#4 (20%): 1.0s , <10M

Hint ：

範例一說明：1(00) -> 3(10) -> 4(11)，總和 8，括弧內為節點邊號的二進位。

範例二說明：1(000)-> 5(100) -> 7(110) -> 8(111)，總和 21。

Tags:

出處:

AP325 [管理者：

mcjksieu005 (mcjksieu005)

]

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