Content:
简体中文
王先生是一位收藏家,他收集了非常多有名的雕像。某天,為了美觀,他想要將收藏台上的雕像按照某種方式重新擺放,由於雕像都有一定的重量,所以他決定雇用一位年輕人,小明,來幫忙搬雕像。
王先生收藏的雕像目前是以隨機的方式放在收藏台上,收藏台的位置由左至右成一列排開,編號依序為 1, 2,..., n,每個收藏台上放置一個雕像,而收藏台 i (1≤i≤n)上目前放的雕像編號為 Si,其高度為 hi 公分,重量為 wi 公斤。王先生要求小明依照下列方式去重新擺放雕像:
為了節省搬運的距離,小明希望你替他寫出一個程式,根據上述方式將雕像重新擺放在收藏台上且搬動的總距離為最短。本題假設任二相鄰收藏台的距離為 1 公尺。
以下為一個範例,假設有 5 個收藏台,雕像 Si (1≤i≤5)的高度和重量以(hi, wi)表示,並依序為(5,20),(10,25),(78,40),(25,25),(5,15)。一種搬動方式如圖(a)所示,搬動的總距離為 12 公尺,而另一種搬動方式如圖(b)所示,搬動的總距離為 8 公尺,是所有符合搬動方式中的最短距離。
Input:
Output:
Sample Input:
輸入1: 5 5 20 10 25 78 40 25 25 5 15 輸入2: 8 5 15 3 5 9 13 13 20 24 30 40 50 9 12 5 15
Sample Output :
輸出1: 8 輸出2: 18
Hint
:
Author
: