同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2057_多元Huffman编码变形

2022-5-16 18:18| 发布者: Hocassian| 查看: 50| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504284276500-Problem List-采集的数据-后羿采集器.html

Pro.ID

2057

Title

多元Huffman编码变形

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2057

AC

Submit

Ratio

时间&空间限制

Time Limit: 1000/500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

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

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

输入

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

输出

Description

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

Input

输入的第一行有一个正整数n，表示有n堆石子。第二行有n个数，分别表示每堆石子的个数。第三行有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

Author

John

样例输入