首页 > 试题广场 >

合并金币

[编程题]合并金币
  • 热度指数：1768 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解

 有 N 堆金币排成一排，第 i 堆中有 C[i] 块金币。每次合并都会将相邻的两堆金币合并为一堆，成本为这两堆金币块数之和。经过N-1次合并，最终将所有金币合并为一堆。请找出将金币合并为一堆的最低成本。

其中，1 <= N <= 30，1 <= C[i] <= 100


输入描述:
第一行输入一个数字 N 表示有 N 堆金币
第二行输入 N 个数字表示每堆金币的数量 C[i]


输出描述:
输出一个数字 S 表示最小的合并成一堆的成本
示例1

输入

4
3 2 4 1

输出

20
示例2

输入

30
10 20 30 40 50 60 70 80 90 100 99 89 79 69 59 49 39 29 19 9 2 12 22 32 42 52 62 72 82 92

输出

7307
算法知识视频讲解
开通博客

暂无题解

问题信息

C++工程师 美团 2020 Java工程师
上传者：小小
难度：
19条回答 7369浏览

热门推荐

通过挑战的用户

相关试题

合并金币

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号