ビルの飾りつけ (Building)
時間制限 : 1sec / スタック制限 : 64MB / メモリ制限 : 64MB
国際情報オリンピックが日本で開かれることとなり，世界の選手達を歓迎するため，空港から宿泊施設までの道沿いにある高層ビルを飾りつけることにした．ある著名なデザイナーにデザインを依頼したところ，飾りつけに利用するビルは，空港から宿泊施設に向けて高くなっていく必要があると言った．つまり，飾りつけに利用するビルの高さを，空港に近いものから順にh1, h2, h3, · · · とおくと，h1 < h2 < h3 < · · · となっていなければならない．
できるだけ飾りつけを華やかにするため，飾りつけに利用するビルの数をできるだけ多くしたい．入力として全てのビルの高さが与えられたとき，利用することのできるビルの数の最大値を計算するプログラムを作れ．
入力
入力ファイルbuilding.in の1 行目には，1 つの整数n (1 ≦ n ≦ 1000) が書かれている．これは，空港から宿泊施設までの道のりにあるビルの数がn であることを表す．
次のn 行には，それぞれのビルの高さが書かれてる．i + 1 行目(1 ≦ i ≦ n) には1 つの整数ai(1 ≦ ai ≦ 10000) が書かれている．これは，空港からi 個目のビルの高さがai であることを表す．
出力
出力は，標準出力に行うこと．飾りつけに利用することのできるビルの数の最大値を表す整数を出力せよ．
入出力例
| 入力例1 |
出力例1 |
9
3
7
5
9
8
10
10
11
9 |
5 |
ビルの総数が9 であり、高さが空港に近いものから順に3, 7, 5, 9, 8, 10, 10, 11, 9 である場合を示したのが下図である. 色をつけて示したビルを選ぶことにより、飾り付けに利用するビルの数を最大にすることができる.このときの最大値は5 である.
コメント
最終更新：2013年02月23日 16:08
