o344.
超市掃貨
Content
廚師大黑拿到了新配方--酪梨披薩！因此廚師大黑決定去超市掃貨。
超市裡有n個酪梨攤販排成一排，第$i$間酪梨攤販賣的酪梨大小為$w_i$。
廚師大黑對酪梨獨具慧眼，他會選擇購買任意長度的一排連續攤販的酪梨，並將他們混在一起變成巨大酪梨來製作頂尖披薩，當然只選擇一間的酪梨也是可以的。
經過大黑長久以來的研究，他知道一個巨大酪梨的美味度會是被選擇的酪梨的大小總和乘上最小的酪梨，大黑想從很多個選擇中合成出能讓美味度最高的巨大酪梨，請你幫他計算出他能獲得的最高美味度是多少？
Input
第一行數字$t$，代表總共有$t$筆測資
每筆測資中:
第一行為$N$
第二行有$N$個數字，表示每個酪梨的大小$w_i$
$1 \le N\le 10^6$
$1 \le a_i \le 3 \times 10^6$
保證$t$筆測資中$N$總和 $\le 10^6$
Output
輸出最大的$美味度$
Sample Input
#1
2 5 1 1 1 1 1 3 1 2 3
Sample Output
#1
5 10
測資資訊：
記憶體限制：
256
MB
公開 測資點#0 (10%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (70%): 1.0s , <10M
公開 測資點#0 (10%): 1.0s , <10M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (70%): 1.0s , <10M
Hint ：
子題1:
${p_1}\le{p_2}\le...\le{p_n}$
10分
子題2:
$t$筆測資中$N$總和 $\le 3000$
20分
子題3:
原題
70分
Tags:
出處:
[管理者：
CGSH
(快加油吧~~)
]
| ID | User | Problem | Subject | Hit | Post Date |
| 45903 |
|
o344 | 85 | 2025-04-26 22:33 |