d049: Q_4_6 少林寺的自動寄物櫃(APCS201710)
Tags : ch4
Accepted rate : 2人/2人 ( 100% ) [非即時]
評分方式:
Tolerant

最近更新 : 2023-03-25 20:31

Content

少林寺的自動寄物櫃系統存放物品時,是將 $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$ 次。我們有兩個可能的擺放順序 (由上而下): 

  • $(1,2)$,也就是物品 $1$ 放在上方,$2$ 在下方。那麼,取用 $1$ 的時候不需要能量, 而每次取用 $2$ 的能量消耗是 $w(1)=1$,因為 $2$ 需取用 $f(2)=4$ 次,所以消耗能量數為 $w(1) \times f(2)=4$。 
  • $(2,1)$。取用 $2$ 的時候不需要能量,而每次取用 $1$ 的能量消耗是 $w(2)=2$,因為 $1$ 需取用 $f(1)=3$ 次,所以消耗能量數 $w(2) \times f(1)=6$。 在所有可能的兩種擺放順序中,最少的能量是 $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 \times 2+(3+4) \times 3=27$。事實上,我們一共有 $3!=6$ 種可能的擺放順序,其中順序 $(3,2,1)$ 可以得到最小消耗能量 $19$。

Input

輸入的第一行是物品件數 $N$,$N < 10^5$。第二行有 $N$ 個正整數,依序是各物品的重量 $w(1)、w(2)、…、w(N)$。第三行有 $N$ 個正整數,依序是各物品的取用次數 $f(1)、f(2)、…、f(N)$ ,重量與次數皆不超過 $1000$,相鄰以空白間隔。

Output

輸出最小能量消耗值。答案不超過 $10^{18}$。 

Sample Input #1
3
3 4 5
1 2 3
Sample Output #1
19
測資資訊:
記憶體限制: 256 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 , <1M
Hint :
Tags:
ch4
出處:
Prof. Wu [管理者:
ktlai (K.我已霸榜.Tlai)
]


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