227. 煉金術

0 Judge

Code: 0


煉金術

煉金術的一個非常重要的原則就是等價交換。今天你有兩個物品$A$、$B$,它們的價值分別是$x$,$y$,那要將$A$、$B$和成為另一個物品$C$所需要花費的代價就會是$x+y$,而且合成出來的物品$C$它的價值為$x+y$。

現在有$N$個物品要合成為一個價值超大的物品,顯然不管合成的順序如何,最終的價值都會相同(也就是$N$個物品的總和),但是過程消耗的代價卻不一樣,因此我們會希望代價越小越好。現在這$N$個物品被排成一排,而且只有相鄰的兩個物品可以進行合成,請問將這$N$個物品全部合成所需的最小代價是多少呢?

輸入說明

第一行為一個正整數$T(T \leq 10)$,表示共有$T$筆測資。 每筆測資第一行包含一個正整數$N$,表示共有$N$個物品要合成,$1 \leq N \leq 100$。 每筆測資第二行為$N$個正整數,表示排成一列之後的物品依序的價值$a_1,a_2,...,a_N$,$1 \leq a_i \leq 1000$。

輸出說明

對於每筆測資,輸出最少需要多少代價。

範例輸入

範例輸出

提示

第一筆測資中,只有兩種合成的方法:

  • 先合成1、2,產生出價值為3 的物品,再合成3、3,需要(1+2)+(3+3)=9單位的代價
  • 先合成2、3,產生出價值為5 的物品,再合成1、5,需要(2+3)+(1+5)=11單位的代價

最小值為9。


Judge Setting

run-time limit: 70 ms
memory limit: 512000 byte
測資數量: 0