#O1097. 玩具装箱
玩具装箱
题目描述
有 个玩具,第 个长度 。要把它们按顺序装进若干箱子,箱子的长度不超过 。若第 到第 个玩具装进一个箱子,则这个箱子的费用为
求把所有玩具装箱的最小总费用。
输入格式
第一行两个整数 。
第二行 个整数 。
输出格式
一行一个整数,表示最小总费用。
样例 #1
样例输入 #1
2 0
1 2
样例输出 #1
5
数据规模与约定
| 数据范围 | 说明 |
|---|---|
| 玩具个数 | |
| 箱子容量 | |
| 每个玩具的长度 |
- 会超时,需要斜率优化把转移降到 ;决策点随 单调,可以用单调队列维护下凸壳。