1719 測資加強 已 rejudge
1637 . 我愛台灣
TopCoder
Tags
Description
自從帳號被刪掉之後, 修羅少年越加的愛台灣.
而看到處於如此危險局面的台灣, 修羅少年決定幫助台灣建立防線的連絡網.
現在修羅少年已經選定了 n 個排成一條線的軍事基地,
打算在這 n 個軍事基地中任兩個之間都建立連絡網.
然而事情並沒有這麼簡單, 兩個相鄰的軍事基地之間都會有一些障礙,
每團障礙都會有一個 G 值, 代表連絡網的電波強度至少要為 G 才能穿過它.
而且如果要在某兩個軍事基地 a, b 之間建立連絡網,
電波必須強到能穿越 a 到 b 間所有障礙才行.
現在修羅少年已經找出了這 n - 1 團障礙的 G 值分別是多少,
請問建立起來的連絡網, 所有電波強度的總和至少是多少?
Input Format
第一行有一個正整數 n
第二行開始有 n - 1 個整數,
其中第 i 個數字代表軍事基地 i 與 i + 1 之間的障礙的 G 值
(1 <= n <= 1000000, 0 <= 任意G <= 231 - 1)
至少有 40% 的測資 n <= 2000
至少有 80% 的測資 n <= 200000
Output Format
請輸出一個數字代表所有電波強度的總合至少是多少.
(保證答案不會超過263 - 1)
Sample Input 1
6
4 3 2 4 3
4 3 2 4 3
Sample Output 1
55
Hints
Problem Source
原TIOJ1637 / Problem Setter: worm
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 10 |
| 2 | 1 | 10 |
| 3 | 2 | 10 |
| 4 | 3 | 10 |
| 5 | 4 | 10 |
| 6 | 5 | 10 |
| 7 | 6 | 10 |
| 8 | 7 | 10 |
| 9 | 8 | 10 |
| 10 | 9 | 10 |