P1295 [TJOI2011]书架

    • 111通过
    • 429提交
  • 题目提供者 elijahqi
  • 评测方式 云端评测
  • 标签 各省省选 2011 天津 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    由于最近又购买了很多书,所以你打算在自己的书房做一个新书架,但是由于墙体高度有限,并且为了照顾整体效果,你希望你的书架的宽度越小越好,所谓宽度就是指书架在垂直方向上占据的距离。

    现按一定顺序给出所有要放置于书架上的书,要求求书架的最小宽度。每本书都有一个长度,而书架是「目」字形的,一层的宽度不能小于其上所摆放的任何一本书的长度。每本书的重量和它的长度成正比,而每层书架都有同样的最大承重,简单起见,换算成长度单位,记为m,也就是说每层上的书的长度之和不得超过m。整个书架的宽度为其上所有层的宽度之和。为了便于查找,任何层上的书必须为给出的书中的连续几本。

    输入输出格式

    输入格式:

    第一行有两个正整数n、m。接下来有n行,每行一个正整数hi,i从1到n,hi ≤ m。

    输出格式:

    共一行,一个整数表示书架的最小宽度。

    输入输出样例

    输入样例#1: 复制
    4 6
    1
    3
    3
    1
    输出样例#1: 复制
    5

    说明

    对于30%的数据,n ≤ 1,000。

    对于100%的数据,n ≤ 100,000,hi ≤ 10,000,m ≤ 1,000,000,000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。