d665. 數字合併 - 高中生程式解題系統

內容

黑板上有n個數字寫成一排，現在每次選擇兩個相鄰的數字，把比較小的那個數字擦掉(如果兩個數字一樣大，那麼擦掉任何一個都可以。)然而，這些步驟需要花費，這個花費恰好等於留下來的那個數字(比較大的那個)。

請問經過n-1次操作，黑板上會剩下的那個數字是多少？

你以為問題這麼簡單嗎？錯!

真正的問題是：

請問經過n-1次操作，黑板上會剩下最大的那個數字，所有操作方法中，最小總花費是多少？

輸入說明

輸入檔只包含一筆測試資料。
第一列有一個正整數n(1<=n<=1,000,000)代表黑板上數字的個數。
接下來有n列，每列有一個正整數(1<=數字<=10⁹)依序代表黑板上的每個數字。

輸出說明

請輸出經過n-1次操作之後，所需的最小總花費。

範例輸入 #1

範例輸出 #1

測資資訊：

記憶體限制： 512 MB
不公開測資點#0 (100%): 10.0s , <10M

提示：

消掉4、花費5；
消掉2、花費5；
消掉5、花費5；
消掉5、花費7；
總花費是5+5+5+7=22。

TIOJ 2008例行賽03-Elite (prob G)。BOI 2007 Day2(prob 6,Sequence)。

Problem Setter：Tmt。

標籤:

出處:

TIOJ1225 [管理者： snail (蝸牛) ]

編號	身分	題目	主題	人氣	發表日期
沒有發現任何「解題報告」