1225 . 數字合併

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

92.7% (139/150)

Submission's AC Ratio

45.2% (223/493)

Tags

TIOJcon 2008-TIOJcon-3rd BOI 2007-BOI

Description

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

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

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

真正的問題是：

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

Input Format

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

Output Format

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

Sample Input 1

5
7
4
5
2
5

Sample Output 1

22

Hints

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

Problem Source

原TIOJ1225 / TIOJ 2008例行賽03-Elite (prob G)。BALTIC OLYMPIAD IN INFORMATICS 2007 Day2(prob 6,Sequence)。Problem Setter：Tmt。

Subtasks

No. Testdata Range Score
1 0 5
2 1 5
3 2 5
4 3 5
5 4 5
6 5 5
7 6 5
8 7 5
9 8 5
10 9 5
11 10 5
12 11 5
13 12 5
14 13 5
15 14 5
16 15 5
17 16 5
18 17 5
19 18 5
20 19 5

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1900 65536 262144 1
1 1900 65536 262144 2
2 1900 65536 262144 3
3 1900 65536 262144 4
4 1900 65536 262144 5
5 1900 65536 262144 6
6 1900 65536 262144 7
7 1900 65536 262144 8
8 1900 65536 262144 9
9 1900 65536 262144 10
10 1900 65536 262144 11
11 1900 65536 262144 12
12 1900 65536 262144 13
13 1900 65536 262144 14
14 1900 65536 262144 15
15 1900 65536 262144 16
16 1900 65536 262144 17
17 1900 65536 262144 18
18 1900 65536 262144 19
19 1900 65536 262144 20
Submit
Back to Top