#P1295. [TJOI2011] 书架

[TJOI2011] 书架

题目背景

由于最近又购买了很多书,所以你打算在自己的书房做一个新书架,为了照顾整体效果,你希望你的书架的宽度越小越好。

书架背靠墙摆放,宽度就是指书架在垂直于墙面的方向上占据的距离。

题目描述

现按一定顺序给出所有要放置于书架上的书,共有 nn 本,第 ii 本书有一个长度 hih_i

书架有若干层,层与层之间的宽度不一定相等,但是一层的宽度不能小于其上所摆放的任何一本书的长度。同时,每层上的书的长度之和不能超过一个给定的参数 mm,且任何层上的书必须是给出的书的序列中连续的几本。

书架的宽度是所有层的宽度之和,求书架的最小宽度。

输入格式

输入的第一行包含两个整数 nnmm

22 到第 (n+1)(n + 1) 行,每行一个整数,第 (i+1)(i + 1) 行的整数代表第 ii 本书的长度 hih_i

输出格式

输出一行一个整数表示答案。

4 6
1
3
3
1
5

提示

数据规模与约定

  • 对于 30%30\% 的数据,保证 n103 n \leq 10^3
  • 对于 100%100\% 的数据,保证 1n1051 \leq n \leq 10^51hi1091 \leq h_i \leq 10^9maxi=1nhim109\max\limits_{i = 1}^{n} h_i \leq m \leq 10^9

提示

由于原题题意严重模糊不清,现给出简化版题意:

给出一个长度为 nn 的序列 hh,请将 hh 分成若干段,满足每段数字之和都不超过 mm,最小化每段的最大值之和。