遠古時代,烏龜還不會飛,曾有座由 $N$ 個烏龜想要相互堆疊成一座塔。每一隻烏龜可以用兩個屬性來形容:第 $i$ 隻烏龜有一個「重量」 $w_i$ 與一個「過動度」$f_i$。現在,這些烏龜們想要依某種順序堆疊成一個塔,要最少化「麻煩度」。麻煩度的計算方法如下:
對於每一隻烏龜,其「過動度」$f_i$ 代表了它會想要出去幾次。而每次要出去,在其上方的烏龜都必須移開。具體來說,第 $i$ 隻烏龜會想要出去 $f_i$ 次,且每次都要花費 $w_1 + w_2 + w_3 + \dots + w_{i - 1}$ 的麻煩度,總麻煩度 $f_i(w_1 + w_2 + w_3 + \dots + w_{i - 1})$。舉例來說,如果有三隻烏龜烏龜從上到下的重量依序為 $[1, 2, 3]$,過動度為 $[4,5,6]$,則其麻煩度可以計算為 $1 \times 0 + 2 \times 4 + 3 \times (4 + 5) = 35$。
給你這 $N$ 隻烏龜的相關資料,請計算出它們堆疊成塔之後所可以達成的最小「麻煩度」。以上面的例子來說,那三個烏龜的最佳解是從上到下 $w = [3,2,1]$、$f = [6,5,4]$,的話,那麻煩度就是 $3 \times 0 + 2 \times 6 + 1 \times (6 + 5) = 23$(第一個範例測資)。
輸入將有三行。第一行會是 $N$($1 \le N \le 10^ 5$),代表烏龜的數量。接下來第二行會有 $N$ 個正整數 $w_1, w_2, w_3, w_4 ,\dots, w_N$,而第三行也會有 $N$ 個正整數 $f_1, f_2, f_3, f_4 ,\dots, f_N$($1 \leq w_i, f_i \leq 1000$)。
此外:
請輸出一個數字代表答案。
APCS 2017.10.18
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0~1 | 範例測資 | 0 |
2 | 2~6 | $N = 2$,且取用次數 $f_1=f_2=1$。 | 10 |
3 | 7~13 | $N = 3$ | 20 |
4 | 2~6, 14~20 | $N \le 1000$,且每一個物品 $i$ 的取用次數 $f_i=1$ | 45 |
5 | 0~29 | 無額外限制 | 25 |