d665: 數字合併
標籤 :
通過比率 : 66人/75人 ( 88% ) [非即時]
評分方式:
Tolerant

最近更新 : 2010-06-01 00:19

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

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

你以為問題這麼簡單嗎?!

真正的問題是:

請問經過n-1次操作,黑板上會剩下最大的那個數字,所有操作方法中,最小總花費是多少?
輸入說明
輸入檔只包含一筆測試資料。
第一列有一個正整數n(1<=n<=1,000,000)代表黑板上數字的個數。
接下來有n列,每列有一個正整數(1<=數字<=109)依序代表黑板上的每個數字。
輸出說明
請輸出經過n-1次操作之後,所需的最小總花費。
範例輸入
5
7
4
5
2
5
範例輸出
22
測資資訊:
記憶體限制: 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 (蝸牛)
]


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