i792: pB. 造橋人,我的超人
Tags : Greedy
Accepted rate : 19人/21人 ( 90% ) [非即時]
評分方式:
Tolerant

最近更新 : 2022-09-15 11:30

Content

造橋人的使命就是造橋。

 

現在有 N 塊板子,每塊板子長度 Li
每回合,造橋人會選擇一塊還沒被使用的板子用來造橋。
為了感謝造橋人的辛勞,各區的民眾準備了 N 份禮物要給他。
每當造橋人搭建一塊板子,大家就會給他一份重量 Wi 的謝禮。

 

造橋人會把所得到的禮物扛在身上,並往前繼續造橋。
其中,當扛著總重 W 的謝禮,走過 L 長的距離時,將對應付出 W x L 單位的體力。

 

因為每一區民眾的禮物都已經準備好,所以 N 份禮物的獲得順序不能變動;
但是造橋人可以改變所使用的木板順序。

 

舉例來說,假設 N = 3,
N 塊板子分別為:板子0(長度2), 板子1(長度6), 板子2(長度8)
N 個禮物分別為:禮物0(重量7), 禮物1(重量5), 禮物2(重量3)

假設造橋順序為:板子0 → 板子1 → 板子2

則耗費的體力將為:
搭建板子0,並且手上沒有任何禮物:0  x L0 = 0  x 2 = 0
搭建板子1,並且手上擁有禮物0  :7  x L1 = 7  x 6 = 42
搭建板子2,並且手上擁有禮物0,1 :12 x L2 = 12 x 8 = 96
完成搭建,並且手上擁有禮物0,1,2:15 x 不走動 = 15 x 0 = 0
也就是總共付出 0 + 42 + 96 + 0 = 138 單位的體力

 

但若改為造橋順序:板子2 → 板子1 → 板子0

則耗費的體力將為:
搭建板子2,並且手上沒有任何禮物:0  x L2 = 0  x 8 = 0
搭建板子1,並且手上擁有禮物0  :7  x L1 = 7  x 6 = 42
搭建板子0,並且手上擁有禮物0,1 :12 x L0 = 12 x 2 = 24
完成搭建,並且手上擁有禮物0,1,2:15 x 不走動 = 15 x 0 = 0
也就是總共付出 0 + 42 + 24 + 0 = 66 單位的體力


可以看出 板子2 → 板子1 → 板子0 會是比較好的木板使用順序。

 

在禮物獲得順序不能被變動的情況,
請協助計算最佳木板使用順序策略下,造橋人所必須付出的最小體力值。

 

謝謝你
造橋人,我的超人

Input

第一行有一個正整數 N,代表木板和禮物總數
1 ≤ N ≤ 105

第二行由左至右有 N 個正整數 Li,代表可使用的木板長度
1 ≤ Li ≤ 1000

第三行由左至右有 N 個正整數 Wi,代表依序獲得的禮物重量
1 ≤ Wi ≤ 1000

Output

最小所需付出體力值

Sample Input #1
3
2 6 8
7 5 3
Sample Output #1
66
Sample Input #2
3
2 2 2
7 5 3
Sample Output #2
38
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (5%): 2.0s , <1K
公開 測資點#1 (5%): 2.0s , <1K
公開 測資點#2 (5%): 2.0s , <1K
公開 測資點#3 (5%): 2.0s , <1K
公開 測資點#4 (5%): 2.0s , <1K
公開 測資點#5 (5%): 2.0s , <1K
公開 測資點#6 (5%): 2.0s , <1K
公開 測資點#7 (5%): 2.0s , <1K
公開 測資點#8 (5%): 2.0s , <1K
公開 測資點#9 (5%): 2.0s , <1K
公開 測資點#10 (5%): 2.0s , <1M
公開 測資點#11 (5%): 2.0s , <1M
公開 測資點#12 (5%): 2.0s , <1M
公開 測資點#13 (5%): 2.0s , <1M
公開 測資點#14 (5%): 2.0s , <1M
公開 測資點#15 (5%): 2.0s , <1M
公開 測資點#16 (5%): 2.0s , <1M
公開 測資點#17 (5%): 2.0s , <1M
公開 測資點#18 (5%): 2.0s , <1M
公開 測資點#19 (5%): 2.0s , <1M
Hint :

10%:所有 Li 皆相同
10%:Li 只有兩種

30%:N ≤ 100
50%:無特別限制 

Tags:
Greedy
出處:
111學年度hgsh校內賽 [管理者: mushroom.cs9...(mushroom) ]


ID User Problem Subject Hit Post Date
32189 mushroom.cs9...(mushroom) i792
題解
25 2022-09-20 09:55