← 返回题目列表

AtCoder · joisc2007_buildi

building. 建筑装饰(建筑)

中文机器翻译题面 查看原题

以下是来自日本的官方日本新闻原版PDF,已完整保存并按原样染色。

ビルの飾り付け (Building) - 原题 PDF 第 1 页
原题PDF第1页
ビルの飾り付け (Building) - 原题 PDF 第 2 页
原题PDF第2页
可复制的 PDF 提取文本
Building: ビルの飾りつけ


input ファイル“building.in”
output 標準出力
ソースファイルbuilding.c/building.cpp/Building.java
時間制限1 秒/ データ


 国際情報オリンピックが日本で開かれることとなり,世界の選手達を歓迎するため,空港か

ら宿泊施設までの道沿いにある高層ビルを飾りつけることにした.ある著名なデザイナーにデ

ザインを依頼したところ,飾りつけに利用するビルは,空港から宿泊施設に向けて高くなって

いく必要があると言った.つまり,飾りつけに利用するビルの高さを,空港に近いものから順

にh1, h2, h3, · · · とおくと,h1 < h2 < h3 < · · · となっていなければならない.

 できるだけ飾りつけを華やかにするため,飾りつけに利用するビルの数をできるだけ多くし

たい.入力として全てのビルの高さが与えられたとき,利用することのできるビルの数の最大

値を計算するプログラムを作れ.

Input. 入力ファイルbuilding.in の1 行目には,1 つの整数n (1 ≦n ≦1000) が書かれてい

る.これは,空港から宿泊施設までの道のりにあるビルの数がn であることを表す.

 次のn 行には,それぞれのビルの高さが書かれてる.i + 1 行目(1 ≦i ≦n) には1 つの整数

ai(1 ≦ai ≦10000) が書かれている.これは,空港からi 個目のビルの高さがai であることを

表す.


Output. 出力は,標準出力に行うこと.飾りつけに利用することのできるビルの数の最大値

を表す整数を出力せよ.


例


 building.in 標準出力
 9            5
 3
 7
 5
 9
 8
 10
 10
 11
 9

                    ビルの飾りつけ–1/2

ビルの総数が9 であり、高さが空港に近いものから順に3, 7, 5, 9, 8, 10, 10, 11, 9 である場合

を示したのが下図である。色をつけて示したビルを選ぶことにより、飾り付けに利用するビル

の数を最大にすることができる。このときの最大値は5 である。





            空港                宿泊施設





                    ビルの飾りつけ–2/2