设有一个长度为 的钢条,在钢条上标有 个位置点 。现在需要按钢条上标注的位置将钢条切割为 段,假定每次切割所需要的代价与所切割的钢条长度成正比。请编写一个算法,能够确定一个切割方案,使切割的总代价最小。
注意:此题目数据范围增大至 。为了减小实现难度,如果有多种最优答案,任意输出一种即可
第一行两个整数 ,
第二行 个整数
第一行一个整数,表示最小切割代价
第二行 个整数,其中第 个整数 表示第 次切割点的索引值,
如果有多种最优答案,任意输出一种即可
输入样例 1:
4 10 3 4 7 9
输出样例 1:
23 2 1 3 4