問題文
所以,1 我决定制作一堆纸板箱,而不是一个接一个地摊开盒子。然而,纸板有固定的重量,如果你在上面堆放比下面的纸板重的纸板,下面的纸板就会塌陷。
图表:底部纸板的重量必须大于顶部纸板的重量
纸板箱的重量是按照从卡车上运输的顺序给出的,因此请考虑如何以不会压坏纸板箱的方式堆放纸板箱。然后,求堆积的山的数量最少时的山的数量。 有一条
入力
N w_1 w_2 : : w_N
- 输入是 N+1 行。
- 1 行包含一个表示纸板箱数量的整数。 来自行 N(1≦N≦50) 。 来自行
- 2 从线 N 行包含 上线i+1(1≦i≦N) 在行中 i 表示要承载的纸板重量的整数。 w_i(1≦w_i≦100,000) 。 来自行
出力
请在末尾输出换行符。
入力例 1
5 4 3 1 2 1
出力例 1
2
- 如果按照下例所示的顺序堆叠它们,2 将创建两堆纸板。
- 3 旁边纸箱的重量 2 纸板不能堆放在上面,所以 1 不能是一堆,最小为 2 变为。
入力例 2
7 93 249 150 958 442 391 25
出力例 2
3
- 当按照下图所示的形状堆叠时,山的数量为 3 变为。
更正:下图中的225纸板箱是25错误。非常抱歉。
入力例 3
4 100 100 100 100
出力例 3
1
- 相同重量的纸板箱可以堆叠在一起,因此1 可制成一堆。
入力例 4
6 5 10 15 20 25 30
出力例 4
6
- 由于没有一个纸板箱可以堆叠在前一个纸板箱之上,1 我无法将它们全部堆叠在一起。
- 因此,6 一座山是最少的。
入力例 5
15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9
出力例 5
6
- 如下图所示堆叠时,变为最小值。