e898: 抽抽樂 獎不完
Tags :
Accepted rate : 4人/15人 ( 27% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-02-19 16:13

Content

桌上有 N 張卡片,每張卡片上都有標註一個大於 0 的整數,參與者要不停的從中抽掉一張卡片(不再放入其中),

而獲得的累加獎金數為此張卡片的左右兩張卡片的點數乘積。

注意第一張卡片與最後一張卡片不能抽取,抽到最後也是只剩下這兩張卡片,請問最後可獲得的獎金最大值為何?

 

<例如>有 5 張卡片:  5  10  7  8  4

抽卡的順序可以如下

10 -> 7 -> 8  ---> 獎金 = 35 + 40 + 20 = 95  

10 -> 8 -> 7  ---> 獎金 = 35 + 28 + 20 = 83  

8 -> 7 -> 10  ---> 獎金 = 28 + 40 + 20 = 88

事實上,如下的抽取順序可以獲得最多的獎金  

7 -> 8 -> 10 --->  獎金 = 80 + 40 + 20 = 140

 

 

 

Input

多筆測資,每筆測資兩行,

第一行一個整數 N (N<=1000),

第二行有 N 個整數 (1~100)

EOF 結束

Output

每筆測資一行輸出,可以獲得的最大獎金數。

Sample Input #1
4
3 5 10 9
5
5 10 7 8 4
5
5 10 7 8 6
Sample Output #1
72
140
170
測資資訊:
記憶體限制: 64 MB
不公開 測資點#0 (25%): 1.0s , <1K
不公開 測資點#1 (25%): 1.0s , <1K
不公開 測資點#2 (25%): 1.0s , <1M
不公開 測資點#3 (25%): 1.0s , <1M
Hint :
Tags:
出處:
林口高中校內選訓 [管理者:
hshua (hshua)
]


ID User Problem Subject Hit Post Date
20632
hshua (hshua)
e898
解法之一
220 2020-02-14 21:17