Problem 1378 --算法实现题 4-20 多元 Huffman 编码变形

1378: 算法实现题 4-20 多元 Huffman 编码变形

上一题 正确率: $0.00\%$ 下一题
"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $2$ 正确数量 $0$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 贪心

Description

在一个操场的四周摆放着 n 堆石子。现要将石子有次序地合并成一堆。规定在合并过程中最多可以有 m(k)次选 k 堆石子合并成新的一堆，2≤k≤n，合并的费用为新的一堆的石子数。

试设计一个算法，计算出将 n 堆石子合并成一堆的最小总费用。

算法设计：
对于给定 n 堆石子,计算合并成一堆的最小总费用。

Input

输入的第 1 行有 1 个正整数 n，表示有 n 堆石子。第 2行有 n 个数，分别表示每堆石子的个数。第 3 行有 n-1 个数，分别表示 m(k)（2≤k≤n）的值。

Output

输出最小总费用。问题无解时输出“No solution!”

Sample Input复制

7
45 13 12 16 9 5 22
3 3 0 2 1 0

Sample Output复制

136

推荐代码 查看1378 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$ $ms]
内存最少[$ $KB]
第一AC
第一挑战 计爱玲 113457 2017-07-28 11:14:09

赛题来源/所属竞赛 NA 算法导论(第三版)中文完整高清版

竞赛编号 竞赛名称 竞赛时间 访问比赛