2014 . 2017國手系列3：唬爛接龍
TopCoder
Description
在2017的IOI國手群中有傳奇的事情發生，例如說存在一個三角形的定義完全不同的空間、或者某種會跑的神秘物種等等。然而其中稱得上是經典的，大概就是唬爛了吧！
事情是這樣的。在這個國手群中有個人對唬爛有特殊的喜好，他的經典名句就是：「那你一定在唬爛啊」。當然，好的唬爛也不是隨便說說就可以想到的，因此他們總是會互相交流各式各樣的唬爛，以持續精進唬爛能力。
有一天，這個人突發奇想，想要把很多個唬爛融合在一起，以創造更高品質的唬爛。因此，他們首先選出了$N$則唬爛，並且依照連貫性將這些唬爛排成一排，簡稱「唬爛接龍」。接著，他們可以選擇唬爛接龍中連續三則唬爛，並將中間那則的精髓融合到它的前後兩則唬爛當中，接著把中間那則唬爛拿掉。這個動作可以不斷重複，一直到唬爛接龍中只剩下兩則唬爛為止。
當然，融合唬爛的這個動作是很花時間的，假設選擇的連續三則唬爛的長度分別是$a,b,c$，那他們就需要花$abc$單位的時間完成融合的動作（融合前後唬爛的長度不會改變）。但國手們其實也都很忙，所以不想浪費太多時間做這件事情。因此，你的任務就是寫一個程式計算總花費時間最少的融合方法。
例如若$N=5$，五則唬爛的長度分別是13,17,16,11,15，則可以先選17,16,11，融合後變成13,17,11,15；再選13,17,11，變成13,11,15；最後再選剩下的三則，這樣總共的花費是$17\times16\times11+13\times17\times11+13\times11\times15=7568$，這也是所有融合方法中花費最小的一種。
當然，因為他們是資訊國手的關係，所以也想順便考考你會不會資訊界中非常重要的一種資料結構：二元樹。恰好，假如把「融合」這個動作看成一種兩組唬爛（(前，中)一組、(中，後)一組）進行的二元運算的話，那整個融合過程可以被表示成一個運算式。例如上例中，若把唬爛從0編號到$N-1$，那該融合過程就是$((0,1)+((1,2)+(2,3)))+(3,4)$，可以用運算樹的前序遍歷表示成$+,+,(0,1),+,(1,2),(2,3),(3,4)$。若把所有的$+$換成$-1$，把一組唬爛換成前面那一組的編號，運算式便可以簡記成$-1,-1,0,-1,1,2,3$，稱這是這個融合策略的前序表示法。
因此，請你寫一個函數，計算對於任意的唬爛接龍，花費時間最少的融合方法的前序表示法長什麼樣子。
Input Format
本題沒有輸入，如果你輸入了任何東西可能會導致各種不可預期的結果(?)。
請#include "lib2014.h"之後實作下列一個函數。如果你的函數名稱不對或者長得不像下面那一行，你將會獲得一個CE。
void Solve(int N, __int128 l[], int ans[]);：評分程式會呼叫這個函數，並傳入唬爛接龍的長度$N$以及每則唬爛的長度$l_i$。你必須將你的融合策略的前序表示法（長度$2N-3$）存入陣列ans當中。
在同一次執行中，Solve可能會被呼叫很多次（最多8次），所以請確保這個函數有做好初始化的動作。
對於所有測資，$3\leq N\leq 10^ 6; 1\leq l_i\leq 10^ 9$。
下表中以$C_{\text{opt}}$代表最佳融合策略的總花費時間，$C$代表Solve回傳的融合策略的總花費時間。
| 子任務（測資） | 額外限制 | 分數 |
| 1 (0) | $N=3$ | 1 |
| 2 (0~1) | $N\leq 20$ | 37 |
| 3 (0~2) | $N\leq 500$ | 62 |
| 4 (0~3) | $N\leq 5000$ | 30 |
| 5 (0~4) | $N\leq 10^ 5$ | 42 |
| 6 (5) | $h_i$為非遞減序列 | 17 |
| 7 (5~6) | $h_i$先遞增後遞減 | 56 |
| 8 (7) | 只要$C\leq 2C_{\text{opt}}$就會被視為正確 | 28 |
| 9 (7~8) | 只要$C\leq 1.25C_{\text{opt}}$就會被視為正確 | 32 |
| 10 (0~9) | 無 | 95 |
Output Format
本題沒有輸出，如果你輸出了任何東西，你將會獲得一個WA。
Sample Input 1
2
5
13 17 16 11 15
3
10 20 30
Sample Output 1
-1 -1 0 -1 1 2 3
7568
-1 0 1
6000
Hints
這裡有一個測試用的標頭檔，可以用來測試。
該標頭檔接受的輸入格式如下：
首先輸入$T$（測資筆數）；對於每一筆測資，依序輸入$N,l_0,l_1,\cdots,l_{N-1}$。
對於每一次呼叫Solve函數，此程式會輸出兩行，第一行為回傳的融合策略，第二行為這個融合策略的總花費時間。
以下是一個保證格式正確（不會CE也不會RE、MLE）但只能讓你獲得1分的範例程式：
#include "lib2014.h" void Solve(int N, __int128 h[], int ans[]) { ans[0] = -1; ans[1] = 0; ans[2] = 1; }
Problem Source
Problem Set / Description by Yihda Yol
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 1 |
| 2 | 0~1 | 37 |
| 3 | 0~2 | 62 |
| 4 | 0~3 | 30 |
| 5 | 0~4 | 42 |
| 6 | 5 | 17 |
| 7 | 5~6 | 56 |
| 8 | 7 | 28 |
| 9 | 7~8 | 32 |
| 10 | 0~9 | 95 |