TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1350
  • 题目
  • P1350【USACO 2009 OPEN GOLD-3】干草塔
    限制 : 时间限制 : 15000 MS   空间限制 : 65536 KB
    问题描述

    奶牛们不喜欢黑暗。 为了调整牛棚顶的电灯的亮度,Bessie必须建一座干草堆使得她能够爬上去够到灯泡。一共有N大包的干草(1<=N<=100000)(从1到N编号)依靠传送带按顺序传输到牛棚里面。第i包干草有一个宽度W_i(1<=w_i<=10000)。所有的干草包的厚度和高度都为1.

    Bessie必须利用所有N包干草来建立起干草塔,并且按照他们进牛棚的顺序摆放。她可以想放多少包就放多少包以建立起干草塔的地基(当然是紧紧的放在一行中)。接下来他可以把几个接着送进来的草包放在之前一级的上方来建立新的一级。注意:每一级不能比下面的一级宽。她持续的这么放置,直到所有的草包都被安置完成。她必须按照草包进入牛棚的顺序堆放。说得更清楚一些:一旦她将一个草包放在第二级,她不能将接下来的草包放在地基上。

    Bessie的目标是建立起最高的干草塔——而且她已经知道每个将会被送进来的草包会是多大。她最高可以建多高的塔呢?

    输入格式

    第1行:一个单一的整数N。
    第2~N+1行:一个单一的整数:W_i。

    输出格式

    第1行:一个单一的整数,表示Bessie可以建立的草包堆的最高高度。

    样例输入

    3
    1
    2
    3

    样例输出

    2


    输出说明:
    前两个(宽度为1和2的)放在底层,总宽度为3,在第二层放置宽度为3的。
               +----------+
               |    3     |
               +---+------+
               | 1 |   2  |
               +---+------+


    来源  usaco 2009公开赛金组