AT_arc006_3 [ARC006C] 積み重ね

[problemUrl]: https://atcoder.jp/contests/arc006/tasks/arc006_3 高橋君はもう大人なので、親元を離れて一人暮らしをすることにしました。トラックから引越し先の部屋へと荷物のダンボールを運びたいのですが、部屋の床がダンボールで埋まってしまうと、今日高橋君が寝るための布団がひけません。 そこで、$ 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 ``` ``` 2 ``` - 下図の例の順に積み重ねると、$ 2 $ つのダンボールの山ができる。 - $ 3 $ 番目のダンボールの次に重さ $ 2 $ のダンボールをその上に重ねることはできないので $ 1 $ つの山にすることはできず、最小は $ 2 $ となる。  ``` 7 93 249 150 958 442 391 25 ``` ``` 3 ``` - 下図の形に積み重ねると、山の数は $ 3 $ となる。 訂正：下図の225のダンボールは25の誤りです。申し訳ありません。  ``` 4 100 100 100 100 ``` ``` 1 ``` - 同じ重さのダンボールは積み重ねられるので、$ 1 $ つの山にすることができる。 ``` 6 5 10 15 20 25 30 ``` ``` 6 ``` - どのダンボールも前に運んだダンボールの上に重ねられないので、$ 1 $ つも積み重ねることができない。 - したがって、$ 6 $ つの山が最小となる。 ``` 15 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 ``` ``` 6 ``` - 下図のように積み重ねると最小となる。 

N/A

N/A