d652. 貪婪之糊
標籤 :
通過比率 : 348人/393人 ( 89% ) [非即時]
評分方式:
Tolerant

最近更新 : 2013-11-16 15:12

內容
發客森林,位於艾克隆城附近的一個充滿毒沼和奇怪生物的森林。
這座森林裡有一種奇妙的生物
叫做「貪婪之糊」,是一群非常greedy的醬糊
貪婪之糊之間喜歡玩一個詭異的遊戲
由於兩隻(陀)貪婪之糊包夾另一個貪婪之糊並且把它吸收掉
現在他們的遊戲規則是這樣的
所有的貪婪之糊成一直線排列
每隻貪婪之糊都有不同的大小
可以選擇連續的三個例如A.B.C
由AC包夾吸收掉B
(雖然說是吸收,但是這不會讓A或C的大小增加…因為它們太貪婪了)
然而這麼做會讓沼澤受到污染,污染值P=A的大小×B的大小×C的大小
最後存活下來沒有被吸收掉的那兩陀貪婪之糊就是贏家
但是聰明的你發現這遊戲根本是個陰謀(太可怕了!)
那就是勝利者永遠是最左邊的和最右邊的貪婪之糊

現在的狀況是你誤闖了發客森林
並且目睹了這個奇妙的遊戲(儀式?)
現在有兩陀貪婪之糊想要串通起來贏得這個遊戲
但是不知道要怎麼樣才能讓遊戲造成的污染最小
(他們雖然很貪婪,可是很愛惜他們住的地方)
於是威脅迷路的你
如果不幫他們兩個寫程式算出來的話…
就要把你吸收掉!XD
輸入說明
每個測資點僅一筆測資,無須重複讀入
第一行有正整數n(2<n<=50)表示這一列有幾陀貪婪之糊
第二行有n個正整數A(0<A<100),順序表示這n陀貪婪之糊的大小
輸出說明
請輸出最小污染值(答案保證不超過1000000000)
範例輸入 #1
//sample1
5
1 2 3 4 5

//sample2
7
12 3 5 11 15 5 4
範例輸出 #1
//sample1
38

//sample2
1089
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (75%): 1.0s , <1K
公開 測資點#1 (25%): 1.0s , <1K
提示 :
標籤:
出處:
jack1 [管理者: jack1 (我是韜哥我忘了拿通知單) ]

本題狀況 本題討論 排行

編號 身分 題目 主題 人氣 發表日期
24379 hshua (hshua) d652
DP
1009 2021-02-10 17:21