[USACO Open09]干草塔

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 tower.in 输出文件 tower.out

奶牛们最讨厌黑暗。为了更换牛棚顶部的电灯泡,Bessie必须要用外面一捆捆的干草搭建一个塔爬上去,才能够得到。一共有N(1 <= N <= 100,000)捆干草,编号依次为1~N,它们按顺序放在传送带上运进牛棚里来,第i捆干草的宽度为w_i(1 <= w_i <= 10,000),所有干草的长度和高度均为1。

建塔的时候Bessie必须要把这N捆干草都用上,并要按照它们被运进来的顺序安放,在建第一层(地基)的时候,她可以想放多少捆就放多少捆,必须把它们紧紧地码成一行。她可以把接下来的一些干草码在之前干草的上面以便新建一层,上面的层不能比它下面的层宽,使用这种方法堆叠,直到把所有的干草捆用光。注意,她必须按干草被运进来的顺序来码放它们,建塔的时候也必须从下往上一层一层地进行,比如,假定上一捆干草是放在第二层的,那以后的干草就不可以再放到第一层(即塔基)。

Bessie的目标是要尽可能建一个最高的塔,她事先知道每一捆被放在传送带上运进来的干草的宽度,那么,她究竟可以搭到多高呢?

输入格式:
第1行,一个整数N;
第2~N+1行,第i+1行包含一个整数w_i;

输出格式:
一行,一个整数,即最多可以建多高。

输入输出样例:
tower.in
3
1
2
3

tower.out
2

输出样例解释:
用前两捆做地基,宽度为1+2=3,用第三捆(宽度为3)做第二层,塔高为2。

+----------+
|     3    |
+---+------+
| 1 |   2  |
+---+------+