d081: P-6-20. Hyper-cube path
Tags : DP
Accepted rate : 0人/0人 (0%) [非即時]
評分方式:
Tolerant

最近更新 : 2020-09-23 21:33

Content

一個維度為 n 的 hypercube 是由$2^{n}$個節點組成的網路,每個節點被賦予唯一一個

0~$2^{n}-1$的編號,對於任兩個節點 i 與 j,他們之間會有邊相連若且惟若 i 與 j 的二

進位編碼恰好相差一個位元,我們對於每個節點 i 給予一個正整數的權重 w(i),請

找出編號 0 到編號$2^{n}-1$的一條最短路徑,使得該路徑所經過的點權重總合(包含起

點與終點)為最大。

Input

第一行是正整數 n,第二行則是這$2^{n}$個節點的正整數權重 w(0),

w(1),…,w($2^{n}-1$)數字之間皆以一個空白間隔,其中 n<20 而每個權重值為非負

整數不超過 100。

Output

最大權重總和。

Sample Input
// 1
2
1 2 3 4
// 2
3
1 2 3 4 5 6 7 8
Sample Output
// 1
8
// 2
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 :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


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