华师一附中OI组

标题: 蚂蚁搬沙 [打印本页]

作者: admin 时间: 2018-9-11 16:00
标题: 蚂蚁搬沙
山谷中住着一个巨大的蚂蚁王国，蚁穴外有一个整洁的广场，天气晴好时蚁群常在那里举行各种活动。这天夜里，天降沙尘，第2天，广场上堆满了大大小小的沙堆，蚁哨出去数了数共有n堆，蚁后要求她的臣民将广场上的沙堆清理掉。具体办法是：每次可以把广场上的任意k堆沙子合并成一堆，重复进行直至所有的沙堆最终合并成一堆。规定（1）：2≤k≤m，m由蚁后指定，（2）：每次合并k堆沙子的代价是这k堆沙子的重量和。你的任务是，对给定的n和m，计算出将n堆沙子最终合并成1堆的最小总代价。
例如，广场上有7堆沙子，其重量分别为45，13，12，16，9，5，22。当m=3时，这些沙堆合并成一堆的最小总代价为199。
当m=5时，这些沙堆合并成一堆的最小总代价为148。
输入格式
包含n+2个整数（n≤100000），其中第一行2个正整数，分别表示n堆沙子和每次合并时可以合并的最大堆数m，从第二行开始有n个数，表示n堆沙子的重量（1～500），数与数之间用空格隔开。
输出格式只包含一个正整数，表示将n堆沙子合并成1堆所需的最小总代价。

样例输入
7 3
45 13 12 16 9 5 22

样例输出
199

作者: admin 时间: 2018-9-11 16:00
典型的哈夫曼编码的题目

欢迎光临华师一附中OI组 (http://hsyit.cn/)