d504: 第五題:超立方體的路徑問題
標籤 :
通過比率 : 96% (79 人 / 82 人 ) (非即時)
評分方式:
Tolerant

最近更新 : 2013-04-27 21:59

內容

一個次數為n的超立方體(n-cube)是由2^n,即2的n次方個點組成的圖形,每一個點均由一個n-bits的二元數表示,兩點之間如果其二元數只相差一個bit則有一條邊相連,例如一個2-cube含四個點:00, 01, 10, 11,根據定義共有四個邊:(00,01), (00,10), (01,11), (10,11),一個3-cube則有8個點如右圖所示。對於任何一個n-cube從一點到另一個點可能有許多條路徑,如果兩點相差k個bits,則最短的路徑需要走k個邊,而且會有許多條最短路徑。在3-cube的例子中,由000走到111需走3個邊,一共有6條不同的路徑都是走三個邊。

 

這一題的問題是:給定一個n-cube以及每一個點上的一個權重值,請找出一條由00…0到11…1的最短路徑,使得其所經過的點的權重總合最大。

 

例如上例中如果各點權重為10, 1, 20 100, 30, 5, 5, 10(順序為3-bits轉換為十進制由小到大排列),也就是000的權重為10、001的權重是1、…111的權重是10。最大權重之最短路徑為000 -> 010 -> 011 -> 111,其權重為10+20+100+10=140

 

輸入說明
每一個測試案例一行,第一個數字n代表n-cube,接著有2^n個整數分別代表每一個點的權重(0~1000),其順序是以點的標示的十進制由小到大排列,數字之間皆以一個空白間隔,0<n<10,最後一行只含一個0表示結束。
輸出說明
每一行輸出每一個測試案例的最大權重。
範例輸入
3 10 1 20 100 30 5 5 10
2 0 10 20 0
0
範例輸出
140
20
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 1.0s , <1M
提示 :
標籤:
出處:
98學年度高雄市資訊學科能力競賽 [編輯:
magrady (元元)
]


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」