少林寺的自動寄物櫃系統存放物品時,是將N個物品堆在一個垂直的貨架上,每個物品各佔一層。
系統運作的方式如下:每次只會取用一個物品,取用時必須先將在其上方的物品貨架升高,取用後必須將該物品放回,然後將剛才升起的貨架降回原始位置,之後才會進行下一個物品的取用。
每一次升高貨架所需要消耗的能量是以這些物品的總重來計算。
現在有N個物品,第i個物品的重量是w(i)而需要取用的次數為f(i),我們需要決定如何擺放這些物品的順序來讓消耗的能量越小越好。
舉例來說,有兩個物品w(1)=1、w(2)=2、f(1)=3、f(2)=4,也就是說物品1的重量是1需取用3次,物品2的重量是2需取用4次。
我們有兩個可能的擺放順序(由上而下):
在所有可能的兩種擺放順序中,最少的能量是4,所以答案是4。
再舉一例,若有三物品而w(1)=3、w(2)=4、w(3)=5、f(1)=1、f(2)=2、f(3)=3。
假設由上而下以(3,2,1)的順序,此時能量計算方式如下:取用物品3不需要能量,取用物品2消耗w(3)*f(2)=10,取用物品1消耗(w(3)+w(2))*f(1)=9,總計能量為19。
如果以(1,2,3)的順序,則消耗能量為3*2+(3+4)*3=27。
事實上,我們一共有3!=6種可能的擺放順序,其中順序(3,2,1)可以得到最小消耗能量19。
輸入的第一行是物品件數N,N<1e5。
第二行有N個正整數,依序是各物品的重量w(1)、w(2)、…、w(N)。
第三行有N個正整數,依序是各物品的取用次數f(1)、f(2)、…、f(N),重量與次數皆不超過1000,相鄰以空白間隔。
輸出最小能量消耗值。答案不超過1e18
3 3 4 5 1 2 3
19
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |