原题链接：传送门
Stone
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld
题目描述
有n堆石子排成一排，第i堆石子有ai个石子。每次，你可以选择任意相邻的两堆石子进行合并，合并后的石子数量为两堆石子的和，消耗的体力等价于两堆石子中石子数少的那个。请问，将所有的石子合并成一堆，你所消耗的体力最小是多少？
输入描述
第一行是一个整数T(1≤T≤20)表示样例的个数。
每个样例的第一行是一个整数n(1≤n≤10000),表示石子堆的数量。
第二行是n个整数ai(1≤ai≤10^9)
输出描述
每一行输出样例结果
输入
2
2
1 2
1
1
输出
1
0
说明
巨大的输入，请用c风格进行输入
题目分析
对于n堆石子，我们要从中选择n-1次才能完成对所有石子的合并，那么，最为理想的状态，可以是一个不递减数列或者是一个不递增数列如：2 3 4 9 11 23 65或95 88 41 23 5 1，在这两种情况下，只要从最大的一端开始往左或往右合并，每次消耗掉的体力就是小的那一堆，同时因为每次都是剩余石子与当前最大的那一堆合并，那么这一堆合并后的石子依旧是最大的，所以在这两种情况下，合并所有石子需要消耗的体力是最小的，那就是除去最大那一堆的所有石子的重量的和，我们暂时把这时的消耗成为极限最小体力消耗MIN，那么当每堆石子的数量是打乱的情况下（没有稳定的递增递减关系时是否能通过人为的合并顺序达到极限最小消耗MIN呢？答案是肯定的，对于一个任意给出的数列，如：8 7 6 3 7 9 6，每次找到当前的最大堆，同时看一下它的两边，选二者中大的那一个与之合并，这样能保证数列的初始最大堆每一次都是被包含在当前最大堆当中，且每次都是由这个当前最大堆去和它左边或者右边的较小的堆合并，每次重复这个过程，通过这种方法所消耗的体力便与数列数有序时一样能以极限最小体力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;
}
网友评论