原題鏈接：傳送門
Stone
時(shí)間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 32768K，其他語言65536K
64bit IO Format: %lld
題目描述
有n堆石子排成一排，第i堆石子有ai個(gè)石子妒茬。每次束倍，你可以選擇任意相鄰的兩堆石子進(jìn)行合并，合并后的石子數(shù)量為兩堆石子的和乱顾，消耗的體力等價(jià)于兩堆石子中石子數(shù)少的那個(gè)板祝。請(qǐng)問，將所有的石子合并成一堆走净，你所消耗的體力最小是多少券时？
輸入描述
第一行是一個(gè)整數(shù)T(1≤T≤20)表示樣例的個(gè)數(shù)。
每個(gè)樣例的第一行是一個(gè)整數(shù)n(1≤n≤10000),表示石子堆的數(shù)量伏伯。
第二行是n個(gè)整數(shù)ai(1≤ai≤10^9)
輸出描述
每一行輸出樣例結(jié)果
輸入
2
2
1 2
1
1
輸出
1
0
說明
巨大的輸入橘洞，請(qǐng)用c風(fēng)格進(jìn)行輸入
題目分析
對(duì)于n堆石子，我們要從中選擇n-1次才能完成對(duì)所有石子的合并说搅，那么炸枣，最為理想的狀態(tài)，可以是一個(gè)不遞減數(shù)列或者是一個(gè)不遞增數(shù)列如：2 3 4 9 11 23 65或95 88 41 23 5 1弄唧，在這兩種情況下适肠，只要從最大的一端開始往左或往右合并，每次消耗掉的體力就是小的那一堆候引，同時(shí)因?yàn)槊看味际鞘Ｓ嗍优c當(dāng)前最大的那一堆合并侯养，那么這一堆合并后的石子依舊是最大的，所以在這兩種情況下澄干，合并所有石子需要消耗的體力是最小的逛揩，那就是除去最大那一堆的所有石子的重量的和，我們暫時(shí)把這時(shí)的消耗成為極限最小體力消耗MIN麸俘，那么當(dāng)每堆石子的數(shù)量是打亂的情況下（沒有穩(wěn)定的遞增遞減關(guān)系時(shí)是否能通過人為的合并順序達(dá)到極限最小消耗MIN呢辩稽？答案是肯定的，對(duì)于一個(gè)任意給出的數(shù)列疾掰，如：8 7 6 3 7 9 6搂誉，每次找到當(dāng)前的最大堆，同時(shí)看一下它的兩邊静檬，選二者中大的那一個(gè)與之合并炭懊，這樣能保證數(shù)列的初始最大堆每一次都是被包含在當(dāng)前最大堆當(dāng)中，且每次都是由這個(gè)當(dāng)前最大堆去和它左邊或者右邊的較小的堆合并拂檩，每次重復(fù)這個(gè)過程侮腹，通過這種方法所消耗的體力便與數(shù)列數(shù)有序時(shí)一樣能以極限最小體力MIN將所有的石子堆合并
參考代碼
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
int main(){
int t;
scanf("%d",&t);
while(t--){
int n,m,maxx=0;
scanf("%d",&n);
ll sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&m);
if(m>maxx) maxx=m;
sum+=m;
}
sum-=maxx;
printf("%lld\n",sum);
}
return 0;
}
