題目連結：
題目大意：
第一列給定一正整數 n （1 ≦ n ≦ 1000000），代表有 n 個數字。接著有 n 列輸入，每列給定一正整數（皆介於 1 ～ 10 ^ 9 之間），依序代表 n 個數字的內容。
這 n 個數字依照給定的順序由左至右排。只要數字還剩下超過 1 個，就可以任意挑任意兩個相鄰的數字。比較兩者的大小，將較小的數字從數列中去除。兩者大小一樣，則去除何者都行。而去除數字的操作，其成本為較大的數字之值。
經過 n - 1 次上次的操作，數列只會剩下一個數字，且會有一個這 n - 1 次操作的總成本。試問：總成本最小可為何？
範例輸入：
5
7
4
5
2
5
範例輸出：
22
解題思維：
雖然可以用單調佇列（Monotone Queue）的想法來解，也就是：
我們需要保持一個堆疊（Stack）的遞減性，代表越靠近頂端的數字越小。由左至右掃過這 n 個數字，每掃到一個數字就跟堆疊頂端的元素比較。
如果新數字比頂端大，則刪除頂端（對應到清除較小的數字）；接著看堆疊是否為空。如果為空代表剛剛消除的數字沒有「左邊」的數字，因此成本就是新數字之值；如果不為空，則這個消除的成本就是頂端（也就是「左邊」的數字）與新數字中較小的，因為如果取大的就不會是最小的成本（記住所求是要求最小，而非最大，也就是每次合併的較大數要儘可能地小）。
但是上述步驟作完之後，頂端的元素仍有可能小於新數字。此時就是再重複一次上述的動作，直到新數字可以不破壞遞減性而加入到堆疊裡。
掃完所有數字之後，堆疊很有可能有剩超過 1 個數字。但是因為此時數列已經變為遞減的，所以我們就取最頂端兩個數字合併，而成本就是頂端的下一個數字（因為是合併的兩者中較大）。合併到堆疊剩一個數字時，過程中的所有成本之總和即是所求最小成本。
雖然上述是可行的，而且也不慢（畢竟是線性時間）。但是觀察以下數列經過上述過程的情形：
7 4 5
7 4 5
堆疊為空，直接丟進堆疊裡。
[堆疊]：7
7 4 5
比堆疊頂端的數字小，所以放進堆疊。
[堆疊]：7 4
7 4 5
比堆疊頂端數字大，丟掉堆疊頂端的數字並與新的頂端比較：7 ＜ 5 ，所以此次成本為 5 。並將 5 放入堆疊裡。
[堆疊]：7 5
沒有新數字了，而堆疊裡的數字量 ＞ 1 ，因此取頂端兩個數字 7 5 。削掉 5 ，成本為 7 。此時堆疊大小為 1 。總成本為 7 + 5 。剛好是原有數列 4 兩邊的數字。
讓我們再看看更多（以下不列出過程說明）：
7 4 5 2 5
7 4 5 2 5
[堆疊]：7
總成本：0
7 4 5 2 5
[堆疊]：7 4
總成本：0
7 4 5 2 5
[堆疊]：7 5
總成本：0 + 5
7 4 5 2 5
[堆疊]：7 5 2
總成本：5
7 4 5 2 5
[堆疊]：7 5 5
總成本：5 + 5
[堆疊]：7 5
總成本：10 + 5
[堆疊]：7
總成本：15 + 7
所求 ＝ 22
你可能會注意到這個成本是 4 、 2 各自兩邊的較大的數字之和。對於 4 ，旁邊有 7 跟 5 ；對於 2 旁邊有兩個 5 。而成本剛好是 7 + 5 + 5 + 5 。
更精確的是，所求的最小成本恰好為：每個相鄰數對之中，取出較大的數字並將這些較大的數字總和起來。即給定一數列 A1 、 A2 、 A3 、 …… 、 An，則所求為 max(A1, A2) + max(A2, A3) + …… + max(An-1, An) 。
巧合嗎？當然不是，回到數列為 7 4 5 的那個例子。可以看到在 [堆疊] 為 7 4 ，而新數字為 5 。此時成本為 5 。而在合併堆疊裡的數字—— 7 5 的時候，成本為 7 。4 兩邊的數字都加進去了。
再看例子 7 4 5 2 5 ，[堆疊] 是 7 5 2 ，新數字為 5 ，此時成本為 5 。等到合併堆疊數字頂端的 5 5 合併了，成本為 5 。一樣， 2 兩邊的數字也進去了。
因此，我們可以看到對於一個其左邊和右邊都大於自身的數字，左邊和右邊的數字一個都會作為成本的值出現。只是一個出現在掃瞄數字並合併的時候，一個是掃完數字在合併堆疊的時候。符合 max(左邊, 自身) + max(自身, 右邊)
那如果這個數字，只有左邊或右邊其中一者大於它。不管是何者，你都會發現自身以及大於它的那兩個數字出現在成本的加總裡。同樣也符合 max(左邊, 自身) + max(自身, 右邊)。
至於自身大於左邊和右邊也同樣符合。只有右邊或左邊數字的（也就是最左邊的數字以及最右邊的數字），同樣也符合。
對於所有數字都符合，因此每個相鄰數對之中，取較大數字並將這些較大的數字全部總和起來才剛好是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
