#Î. A Famous City
A Famous City
You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.
Description
先生.B抵达华沙后,他被摩天大楼震惊了,拍了几张照片。但现在,当他看到这些照片时,他惊讶地发现,他甚至无法指出其中的建筑物数量。因此,他决定按如下方式进行处理:
- 将照片从左到右分成n个垂直部分。照片中的建筑物可以被视为矩形,其下边缘是地平线。一个建筑物可以跨越几个连续的部分,但每个部分只能包含一个可见的建筑物,或者根本没有建筑物。
- 测量该作品中每栋建筑的高度。
- 编写一个程序来计算建筑物的最小数量。 先生.B已经完成了前两个步骤,最后一个步骤来到你身边。
Format
Input
T 组测试数据,每个测试用例都以一行开头,其中包含一个整数 n (1 <= n < = 100,000)。下面是一行包含 n 个整数 - 分别是每块建筑的高度。请注意,零高度意味着这件作品中根本没有建筑物。所有输入数字都将是非负数,并且小于 1,000,000,000。
Output
对于每个测试用例,在照片中显示一行,其中包含案例编号和最小可能数量的建筑物。
输出样例的图例
Samples
2
3
1 2 3
3
1 2 1
Case 1: 3
Case 2: 2
Hint
The possible configurations of the samples are illustrated below:
Limitation
1s, 1024KiB for each test case.
第七届SWPU-ACM老生预选赛
- Status
- Done
- Rule
- ACM/ICPC
- Problem
- 187
- Start at
- 2022-9-19 14:00
- End at
- 2022-10-28 14:00
- Duration
- 936 hour(s)
- Host
- Partic.
- 45