前副社長的挑戰狀

發布時間: June 27, 2024, 7:51 p.m.   最後更新時間: June 28, 2024, 7:53 a.m.   時間限制: 1000ms   記憶體限制: 128M

由於太久沒有參與社團,我(37th副社長)決定在這次社內賽向各位現任軟研社員發起挑戰,只要你成功AC本題我就會送你一份禮物喔。決定好要接受挑戰了嗎?那就請看題目!

當接下挑戰的瞬間,你被傳送到了一個競技場之中,但並沒有出現想像中的武器或防具,只有一整排的骰子、一個計分版和一個暫時紀錄器,而仔細觀察骰子後發現這是一個不可能存在的1000面骰,上面的數字是1到1000,正當你疑惑之時,角落的喇吧傳來刺耳的聲響:「歡迎來到虛擬競技場,在你面前的道具就是本挑戰會用到的所有物品,接下來請自行閱讀遊戲規則。」

說完的同時一張紙在你面前憑空出現,最上方寫著四個大字:「遊戲規則」,內容如下:

在挑戰開始時,系統會告訴你本次挑戰的難度$n$並投擲$n$顆骰子,然後告訴你依序骰出的值為何,接著你會被輸送帶運送到每顆骰子前,並對該骰子進行以下其中一個操作。

操作一:將當前骰子的數值加到暫時紀錄器並前往下一顆骰子。

操作二:將剩餘所有的骰子數值加總(含當前的骰子)得一數值$k$,且設暫時紀錄器當前數值為$m$,則將$k \times m$的值加到計分板上並將暫時紀錄器歸零。然後前往下一顆骰子。

當對最後一顆骰子做完操作後,會將暫時紀錄器中的數值加到計分板上,此時計分板的分數即為你的得分,當然,分數是越高越好。

了解遊戲規則後,你知道想通過挑戰必須算出最大值,所以請依照遊戲規則算出可能的最大值並通過挑戰吧!

第一行有一正整數$n, n \leq 10^6$,表示遊戲難度為$n$,
第二行會有$n$個正整數,保證每個數都介於$1$至$1000$,表示依序每顆骰子骰到的數值

輸出根據遊戲規則可得的最大值為何
保證答案不超過long long 範圍

複製範例
4
1 2 3 4
25
複製範例
4
4 3 2 1
27
複製範例
5
3 2 1 2 3
36

範測解釋

紅字表示該數字選擇結算(操作二)

範測一:

1 2 3 4

此時可以獲得最大值$(3+4) \times (1+2) + 4 = 25$

範測二:

4 3 2 1

此時可以獲得最大值$(3+2+1) \times 4 + 2 + 1 = 27$

範測三:

3 2 1 2 3

此時可以獲得最大值$(1+2+3) \times (3+2) + 2 \times 3 = 36$

dp 斜率優化

竹中軟研39th競賽組期末競賽