Hyper-cube path (AP325 P-6-20)

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

輸入格式

第一行是正整數 \(n\)，第二行則是這 \(2^n\) 個節點的權重 \(w(0), w(1), \ldots, w(2^n-1)\)，數字之間皆以一個空白間隔。

限制

• \(1 \le n < 20\)。
• 每個權重值為非負整數且不超過 \(100\)。

輸出格式

輸出最大權重總和。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

2
1 2 3 4

範例輸出 1

8

範例輸入 2

3
1 2 3 4 5 6 7 8

範例輸出 2

21

範例說明

範例一：\(1(00) \to 3(10) \to 4(11)\)，總和 \(8\)，括弧內為節點編號的二進位。

範例二：\(1(000) \to 5(100) \to 7(110) \to 8(111)\)，總和 \(21\)。

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 6 章 P-6-20，第 205 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。