1427-小石子游戏


    内存限制:64MB 时间限制:1000ms 特判: No

    通过数:2 提交数:2 难度:4


题目描述:

一群小孩子在玩小石子游戏,游戏有两种玩法。

1)路边玩法

n堆石子堆放在路边,现要将石子有序合并成一堆,规定每次只能移动相邻的两堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费(最小或最大)。

2)操场玩法

一个圆形操场周围摆放着n堆石子,现要将石子有序合并成一堆,规定每次只能移动相邻的堆石子合并,合并花费为新合成的一堆石子的数量。求将这N堆石子合并成一堆的总花费(最小或最大)。


输入描述:

第一行是一个整型数m(m<100)表示共有m组测试数据。
每组测试数据的第一行是一个整数n(0<n<1000)表示石子的堆数。
第2行为n个整数ai((0<ai<1000)),表示第i堆的石子数。

输出描述:

对于每一组输入,输出4个数(路边玩法最小花费,路边玩法最大花费,操场玩法最小花费,操场玩法最大花费)。
每组的输出占一行。

样例输入:

3
6
5 8 6 9 2 3
5
8 7 3 6 10 
4
9 2 15 6

样例输出:

84 129 81 130
77 95 77 108
64 76 60 83

提示:


上传者:rainflychxy

书中题目链接,请点击上面链接访问!

公告

    欢迎使用NYOJ2.0!