OpenJudge

5_C:神奇的能量项链

总时间限制:
1000ms
单个测试点时间限制:
100ms
内存限制:
1000kB
描述

    2053年的地球,人类发现了一种由神秘的能量石组成的项链。项链是一个闭合的环形,项链上两个相邻的能量石能发生聚合反应。

    当两颗能量石聚合的时候能发出他们二者质量总和1000倍的能量并生成新的能量石,新能量石的质量是原来两颗能量石的质量之和。同时人们还发现,这个聚合的过程是可逆的,也就是用全部聚合结束后最终产生的能量,还可以将一个大的能量石分开成两个小的,如果消耗一部分能量后依然有剩余能量则可继续分解能量石,当一个大的能量石分解成2个小的能量石时需要消耗大能量石自身重量大小的能量,如果剩余能量小于一块待分解的能量石的质量,则此待分解的能量石无法分解。

    每一串能量项链的最终稳定状态,就是其最开始的状态。聪明的人类发现当激发能量项链开始聚合并最终得到一块能量石之后,可以用所得的能量的一部分就将能量项链还原。这真是了不起的发现。因为聚合产生能量,如果再分解使能量项链返回初始状态的过程中消耗的总能量小于聚合过程产生的总能量,那么就有多余的能量被释放出来并供人类使用。

    当对能量项链进行一系列聚合分解操作并使能量项链最终达到最初的稳定状态时,人类最多能得到多少能量呢?这就考验你的智慧了,不同的合并和拆分顺序将产生不同的结果。请你写一个算法,完成这个计算。


输入
输入包含多组测试用例。
输入的第一行为整数T(1<=T<=10)表示后面测试用例的数量。后面是各组测试用例。
每组测试用例占两行。
每组测试用例的第一行为一整数N(2<=N<=30)。表示能量项链含有的能量石的个数。
每组测试用例的第二行为N个整数w1,w2,...,wn(每个能量石的重量都大于0并且小于等于100)依次代表N个能量石的重量。
输出
对每一个测试用例必须单独一行输出整数C。C代表经过一系列聚合分解并使能量项链达到最终稳定状态(即初始状态)时所能产生的最大能量。
样例输入
2
3
2 4 6
2
10 10
样例输出
4000
0
提示
如3个能量石(质量分别为2,4,6)组成的项链。
聚合过程有3种:
第一种
2,4聚合产生6000能量,项链状态为6,6.
6,6聚合产生12000能量,聚合完成共释放6000+12000=18000能量。
第二种
4,6聚合产生10000能量,项链状态为2,10.
2,10聚合产生12000能量,聚合完成共释放10000+12000=22000能量。
第三种
2,6聚合(项链是环形)产生8000能量,项链状态4,8.
4,8聚合产生12000能量,聚合完成共释放8000+12000=20000能量。
分解过程也有3种:
第一种
12分解成2,10两颗能量石,消耗12000能量。
10分解成4,6两颗能量石,消耗10000能量,全部分解完成后共消耗12000+10000=22000能量。
第二种
12分解成4,8两颗能量石,消耗12000能量。
8分解成2,6两颗能量石,消耗8000能量,全部分解完成后共消耗12000+8000=20000能量。
第三种
12分解成6,6两颗能量石,消耗12000能量。
6分解成2,4两颗能量石,消耗6000能量,全部分解完成后共消耗12000+6000=18000能量。
采用最优聚合分解方案(第二种聚合方案+第三种分解方案)可得最大能量22000-18000=4000。

3_A :0<A,B<10的6次方

全局题号
5351
添加于
2012-10-17
提交次数
8
尝试人数
2
通过人数
1