比赛场次 413
比赛名称 刷题ing
比赛状态 已结束比赛成绩
开始时间 2018-05-24 20:30:00
结束时间 2018-05-31 22:00:00
开放分组 全部用户
注释介绍
题目名称 石子合并
输入输出 shizi.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 10 简单对比
用户 结果 时间 内存 得分
Gravatar梦那边的美好ET AAAAAAAAAA 0.003 s 0.35 MiB 100
GravatarWangZoB RRRRRRRRRR 0.001 s 4.17 MiB 0

石子合并

★★   输入文件:shizi.in   输出文件:shizi.out   简单对比
时间限制:1 s   内存限制:128 MiB

【题目描述】

设有$N$堆石子排成一排,其编号为$1,2,3,…,n(n<=100)$。每堆沙子有一定的数量。现要将$N$堆沙子并成为一堆。归并的过程只能每次将相邻的两堆沙子堆成一堆(每次合并花费的代价为当前两堆沙子的总数量),这样经过$N-1$次归并后成为一堆,归并的总代价为每次合并花费的代价和。找出一种合理的归并方法,使总的代价最小。

例如:有$3$堆沙子,数量分别为$13,7,8$,有两种合并方案:

第一种方案:先合并$1,2$号堆,合并后的新堆沙子数量为$20$,本次合并代价为$20$,再拿新堆与第$3$堆沙子合并,合并后的沙子数量为$28$,本次合并代价为$28$,将$3$堆沙子合并到一起的总代价为第一次合并代价$20$加上第二次合并代价$28$,即$48$;

第二种方案:先合并$2,3$号堆,合并后的新堆沙子数量为$15$,本次合并代价为$15$,再拿新堆与第$1$堆沙子合并,合并后的沙子数量为$28$,本次合并代价为$28$,将$3$堆沙子合并到一起的总代价为第一次合并代价$15$加上第二次合并代价$28$,即$43$;

采用第二种方案可取得最小总代价,值为$43$。

【输入格式】

输入由若干行组成,第一行有一个整数$n(1≤n≤100)$;表示沙子堆数。第$2$至$n+1$行是每堆沙子的数量。 

【输出格式】

一个整数,归并的最小代价。

【输入样例】

7
13
7
8
16
21
4
18

【输出样例】

239