#P1295. [TJOI2011] 书架
[TJOI2011] 书架
题目背景
由于最近又购买了很多书,所以你打算在自己的书房做一个新书架,为了照顾整体效果,你希望你的书架的宽度越小越好。
书架背靠墙摆放,宽度就是指书架在垂直于墙面的方向上占据的距离。
题目描述
现按一定顺序给出所有要放置于书架上的书,共有 本,第 本书有一个长度 。
书架有若干层,层与层之间的宽度不一定相等,但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时,每层上的书的长度之和不能超过一个给定的参数 ,且任何层上的书必须是给出的书的序列中连续的几本。
书架的宽度是所有层的宽度之和,求书架的最小宽度。
输入格式
输入的第一行包含两个整数 和 。
第 到第 行,每行一个整数,第 行的整数代表第 本书的长度 。
输出格式
输出一行一个整数表示答案。
4 6
1
3
3
1
5
提示
数据规模与约定
- 对于 的数据,保证 。
- 对于 的数据,保证 ,,。
提示
由于原题题意严重模糊不清,现给出简化版题意:
给出一个长度为 的序列 ,请将 分成若干段,满足每段数字之和都不超过 ,最小化每段的最大值之和。